Skip to Main content Skip to Navigation
Conference papers

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
2 C&O - Equipe combinatoire et optimisation
IMJ-PRG - Institut de Mathématiques de Jussieu - Paris Rive Gauche
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.
Document type :
Conference papers
Complete list of metadata
Contributor : Emeric Gioan Connect in order to contact the contributor
Submitted on : Sunday, June 14, 2009 - 5:06:43 PM
Last modification on : Monday, November 30, 2020 - 5:32:04 PM


  • HAL Id : lirmm-00395075, version 1


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. pp.307-311. ⟨lirmm-00395075⟩



Record views