Biology Reference
In-Depth Information
13.3. Complexity Results
The optimization problem (13.9) is a specific type of
fractional 0-1 programming
problem
which is defined as
m
max
w
i
x
i
(13.12a)
i
=1
α
s
j
0
+
i
=1
α
s
ji
x
i
n
s
β
j
0
+
i
=1
β
ji
x
i
≥
subject to
p
s
,
s
=1
,...,S
(13.12b)
j
=1
-hard since linear 0-1 programming is a special class of
Problem (13.12) when
β
ji
=0and
β
j
0
=1for
j
=1
,...,n
s
,
i
=1
,...m
and
s
=1
...,S
. A typical way to solve a fractional 0-1 programming problem
is to reformulate it as a linear mixed 0-1 programming problem, and solve new
problem using standard linear programming solvers (see [10, 11]).
In [3], a linearization technique for a generalized
This problem is
NP
-hard formulation
(13.12) is applied to solve (13.9). In [9] heuristics are proposed for (13.9) and
generalizations. These attempts are appropriate if the problem is
NP
NP
-hard. How-
ever, whether (13.9) itself is
-hard or not was an open question. This chapter
intents to fill this gap by proving the
NP
NP
-hardness of (13.9).
Theorem 13.2.
Feature selection for consistent biclustering (i.e. (13.9)) is
NP
-
hard.
NP
Proof.
To prove that the problem is
-hard, a special case of the problem
is proven to be
-hard. In the case considered, there are 2 samples and
m
features. Suppose that there are two classes and all but one of the features belong
to the same class. Without loss of generality, assume that
m
-th feature belongs to
one class alone and hence it is selected in the optimal solution unless the problem
is infeasible (i.e.,
x
m
=1). Then (13.9b) becomes
m−
1
i
=1
a
i
1
x
i
m−
1
i
=1
x
i
NP
>a
m
1
(13.13)
m−
1
i
=1
a
i
2
x
i
m−
1
i
=1
x
i
<a
m
2
(13.14)
It has to be proven that the decision problem is
NP
-complete in order to prove
that the corresponding optimization problem is
-hard (see [6]). The decision
version of feature selection for consistent biclustering problem is
NP
Search WWH ::
Custom Search