Tropical polar cones, hypergraph transversals, and mean payoff games
arXiv:1004.2778 · doi:10.1016/j.laa.2011.02.004
Abstract
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 that its elements satisfy. We characterize the extreme rays of the polar in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.
27 pages, 6 figures, revised version
References in corpus (10)
- Lectures on 0/1-polytopes
- Duality and separation theorems in idempotent semimodules
- The Minkowski Theorem for Max-plus Convex Sets
- Generators, extremals and bases of max cones
- Computing the vertices of tropical polyhedra using directed hypergraphs
- Minimal half-spaces and external representation of tropical polyhedra
- The number of extreme points of tropical polyhedra
- The tropical analogue of polar cones
- The level set method for the two-sided eigenproblem
- Carathéodory, Helly and the others in the max-plus world
Cited by in corpus (12)
- Computing the vertices of tropical polyhedra using directed hypergraphs
- Tropical linear-fractional programming and parametric mean payoff games
- Best approximation in max-plus semimodules
- The number of extreme points of tropical polyhedra
- Conditional Independence in Max-linear Bayesian Networks
- The level set method for the two-sided eigenproblem
- Combinatorial simplex algorithms can solve mean payoff games
- Tropical Fourier-Motzkin elimination, with an application to real-time verification
- Minimal external representations of tropical polyhedra
- Signed tropical convexity
- Quasi-Leontief utility functions on partially ordered sets I: efficient points
- Quasi-Leontief utility functions on partially ordered sets II: Nash equilibria