66 citations · 468 across the 34 of their papers we have counts for
8 papers · 1 filter
Tropicalization of facets of polytopes
Xavier Allamigeon, Ricardo D. Katz
It is known that any tropical polytope is the image under the valuation map of ordinary polytopes over the Puiseux series field. The latter polytopes are called lifts of the tropic…
Combinatorial simplex algorithms can solve mean payoff games
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
A combinatorial simplex algorithm is an instance of the simplex method in which the pivoting depends on combinatorial data only. We show that any algorithm of this kind admits a tr…
Tropical Fourier-Motzkin elimination, with an application to real-time verification
Xavier Allamigeon, Uli Fahrenberg, Stéphane Gaubert +2
We introduce a generalization of tropical polyhedra able to express both strict and non-strict inequalities. Such inequalities are handled by means of a semiring of germs (encoding…
Tropicalizing the simplex algorithm
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
We develop a tropical analog of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including th…
Minimal external representations of tropical polyhedra
Xavier Allamigeon, Ricardo D. Katz
Tropical polyhedra are known to be representable externally, as intersections of finitely many tropical half-spaces. However, unlike in the classical case, the extreme rays of thei…
Tropical polar cones, hypergraph transversals, and mean payoff games
Xavier Allamigeon, Stephane Gaubert, Ricardo D. Katz
We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities tha…
The number of extreme points of tropical polyhedra
Xavier Allamigeon, Stephane Gaubert, Ricardo D. Katz
The celebrated upper bound theorem of McMullen determines the maximal number of extreme points of a polyhedron in terms of its dimension and the number of constraints which define…
Computing the vertices of tropical polyhedra using directed hypergraphs
Xavier Allamigeon, Stephane Gaubert, Eric Goubault
We establish a characterization of the vertices of a tropical polyhedron defined as the intersection of finitely many half-spaces. We show that a point is a vertex if, and only if,…