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