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
Conference Papers Year : 2009

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

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.
No file

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00395075 , version 1

Cite

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⟩
96 View
0 Download

Share

More