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

A. S. Freire, V. Acuña, P. Crescenzi, C. E. Ferreira, V. Lacroix, P. V. Milreu, E. Moreno, M. F. Sagot

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva


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.

Idioma originalInglés
Título de la publicación alojadaCombinatorial Optimization - Second International Symposium, ISCO 2012, Revised Selected Papers
Número de páginas13
EstadoPublicada - 2012
Publicado de forma externa
Evento2nd International Symposium on Combinatorial Optimization, ISCO 2012 - Athens, Grecia
Duración: 19 abr. 201221 abr. 2012

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen7422 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349


Conferencia2nd International Symposium on Combinatorial Optimization, ISCO 2012


Profundice en los temas de investigación de 'Minimum ratio cover of matrix columns by extreme rays of its induced cone'. En conjunto forman una huella única.

Citar esto