TY - GEN

T1 - Minimum ratio cover of matrix columns by extreme rays of its induced cone

AU - Freire, A. S.

AU - Acuña, V.

AU - Crescenzi, P.

AU - Ferreira, C. E.

AU - Lacroix, V.

AU - Milreu, P. V.

AU - Moreno, E.

AU - Sagot, M. F.

PY - 2012

Y1 - 2012

N2 - Given a matrix S ∈ ℝ m x n and a subset of columns R, we study the problem of finding a cover of R with extreme rays of the cone F = {v ∈ ℝ n | Sv = 0, v ≥ 0}, where an extreme ray v covers a column k if v k > 0. In order to measure how proportional a cover is, we introduce two different minimization problems, namely the minimum global ratio cover (MGRC) and the minimum local ratio cover (MLRC) problems. In both cases, we apply the notion of the ratio of a vector v, which is given by max i v i/min j | vj > 0 v j. We show that these two problems are NP-hard, even in the case in which |R| = 1. We introduce a mixed integer programming formulation for the MGRC problem, which is solvable in polynomial time if all columns should be covered, and introduce a branch-and-cut algorithm for the MLRC problem. Finally, we present computational experiments on data obtained from real metabolic networks.

AB - Given a matrix S ∈ ℝ m x n and a subset of columns R, we study the problem of finding a cover of R with extreme rays of the cone F = {v ∈ ℝ n | Sv = 0, v ≥ 0}, where an extreme ray v covers a column k if v k > 0. In order to measure how proportional a cover is, we introduce two different minimization problems, namely the minimum global ratio cover (MGRC) and the minimum local ratio cover (MLRC) problems. In both cases, we apply the notion of the ratio of a vector v, which is given by max i v i/min j | vj > 0 v j. We show that these two problems are NP-hard, even in the case in which |R| = 1. We introduce a mixed integer programming formulation for the MGRC problem, which is solvable in polynomial time if all columns should be covered, and introduce a branch-and-cut algorithm for the MLRC problem. Finally, we present computational experiments on data obtained from real metabolic networks.

KW - Extreme rays

KW - elementary modes

KW - metabolic networks

UR - http://www.scopus.com/inward/record.url?scp=84865258516&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-32147-4_16

DO - 10.1007/978-3-642-32147-4_16

M3 - Conference contribution

AN - SCOPUS:84865258516

SN - 9783642321467

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 165

EP - 177

BT - Combinatorial Optimization - Second International Symposium, ISCO 2012, Revised Selected Papers

T2 - 2nd International Symposium on Combinatorial Optimization, ISCO 2012

Y2 - 19 April 2012 through 21 April 2012

ER -