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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationCombinatorial Optimization - Second International Symposium, ISCO 2012, Revised Selected Papers
Pages165-177
Number of pages13
DOIs
StatePublished - 2012
Externally publishedYes
Event2nd International Symposium on Combinatorial Optimization, ISCO 2012 - Athens, Greece
Duration: 19 Apr 201221 Apr 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7422 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Symposium on Combinatorial Optimization, ISCO 2012
Country/TerritoryGreece
CityAthens
Period19/04/1221/04/12

Keywords

  • Extreme rays
  • elementary modes
  • metabolic networks

Fingerprint

Dive into the research topics of 'Minimum ratio cover of matrix columns by extreme rays of its induced cone'. Together they form a unique fingerprint.

Cite this