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

Abstract : Given a matrix S∈ℝm ×n and a subset of columns R, we study the problem of finding a cover of R with extreme rays of the cone $\mathcal{F}=\{v \in \mathbb{R}^n \mid Sv=\mathbf{0}, v\geq \mathbf{0}\}$, where an extreme ray v covers a column k if vk>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 $\frac{\max_i v_i}{\min_{j\mid v_j > 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.
Type de document :
Communication dans un congrès
Proceedings of the Second international Symposium on Combinatorial Optimization (ISCO), Apr 2012, Athens, Greece. Springer-Verlag, 7422, pp.165--177, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-32147-4_16〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00763453
Contributeur : Marie-France Sagot <>
Soumis le : lundi 10 décembre 2012 - 18:56:59
Dernière modification le : mardi 20 novembre 2018 - 09:32:15
Document(s) archivé(s) le : lundi 11 mars 2013 - 12:51:00

Fichier

Minimum_ratio_cover_of_matrix_...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alexandre da Silva Freire, Vicente Acuña, Pierluigi Crescenzi, Carlos Eduardo Ferreira, Vincent Lacroix, et al.. Minimum ratio cover of matrix columns by extreme rays of its induced cone. Proceedings of the Second international Symposium on Combinatorial Optimization (ISCO), Apr 2012, Athens, Greece. Springer-Verlag, 7422, pp.165--177, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-32147-4_16〉. 〈hal-00763453〉

Partager

Métriques

Consultations de la notice

601

Téléchargements de fichiers

147