A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements

Emeric Gioan 1 Michel Las Vergnas 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The fully optimal basis of a bounded acyclic oriented matroid on a linearly ordered set has been defined and studied by the present authors in a series of papers, dealing with graphs, hyperplane arrangements, and oriented matroids (in order of increasing generality). This notion provides a bijection between bipolar orientations and uniactive internal spanning trees in a graph resp. bounded regions and uniactive internal bases in a hyperplane arrangement or an oriented matroid (in the sense of Tutte activities). This bijection is the basic case of a general activity preserving bijection between reorientations and subsets of an oriented matroid, called the active bijection, providing bijective versions of various classical enumerative results. Fully optimal bases can be considered as a strenghtening of optimal bases from linear programming, with a simple combinatorial definition. Our first construction used this purely combinatorial characterization, providing directly an algorithm to compute in fact the reverse bijection. A new definition uses a direct construction in terms of a linear programming. The fully optimal basis optimizes a sequence of nested faces with respect to a sequence of objective functions (whereas an optimal basis in the usual sense optimizes one vertex with respect to one objective function). This note presents this construction in terms of graphs and linear algebra.
Type de document :
Communication dans un congrès
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. Elsevier, 34, pp.307-311, 2009, Electronic Notes in Discrete Mathematics
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395075
Contributeur : Emeric Gioan <>
Soumis le : dimanche 14 juin 2009 - 17:06:43
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00395075, version 1

Collections

Citation

Emeric Gioan, Michel Las Vergnas. A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. Elsevier, 34, pp.307-311, 2009, Electronic Notes in Discrete Mathematics. 〈lirmm-00395075〉

Partager

Métriques

Consultations de la notice

117