A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

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

Résumé

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.
Fichier non déposé

Dates et versions

lirmm-00395075 , version 1 (14-06-2009)

Identifiants

  • HAL Id : lirmm-00395075 , version 1

Citer

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⟩
85 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More