Tropical polar cones, hypergraph transversals, and mean payoff games
From MaRDI portal
Publication:550656
DOI10.1016/J.LAA.2011.02.004zbMATH Open1217.14047arXiv1004.2778OpenAlexW1821883734MaRDI QIDQ550656FDOQ550656
Stéphane Gaubert, Ricardo D. Katz, Xavier Allamigeon
Publication date: 13 July 2011
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1004.2778
Recommendations
- Tropical polyhedra are equivalent to mean payoff games
- The tropical analogue of polar cones
- Tropical linear-fractional programming and parametric mean payoff games
- Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
- Minimal half-spaces and external representation of tropical polyhedra
polyhedratropical convexityminimal solutionshypergraph transversalsmax-plus convexitymax-plus semiringminimal hitting sets
Cites Work
- The complexity of mean payoff games on graphs
- Tropical convexity
- Title not available (Why is that?)
- Affine Buildings and Tropical Convexity
- The tropical analogue of polar cones
- The Perron-Frobenius theorem for homogeneous, monotone functions
- Minimax algebra
- Tropical polyhedra are equivalent to mean payoff games
- Title not available (Why is that?)
- Duality and separation theorems in idempotent semimodules.
- Tropical Convex Hull Computations
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Tropical halfspaces
- The maximum numbers of faces of a convex polytope
- Idempotent functional analysis: An algebraic approach
- Minimal half-spaces and external representation of tropical polyhedra
- Generators, extremals and bases of max cones
- Title not available (Why is that?)
- Title not available (Why is that?)
- Scheduling with AND/OR Precedence Constraints
- Stochastic Games with Perfect Information and Time Average Payoff
- Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
- The duality theorem for min-max functions
- A constructive fixed point theorem for min-max functions
- Shelling polyhedral 3-balls and 4-polytopes
- -convexity
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Max-Atom Problem and Its Relevance
- The number of extreme points of tropical polyhedra
- Hard problems in max-algebra, control theory, hypergraphs and other areas
- The Minkowski theorem for max-plus convex sets
- A note on systems with max-min and max-product constraints
- STACS 97. 14th annual symposium on theoretical aspects of computer science. Lübeck, Germany, February 27 -- March 1, 1997. Proceedings
- Carathéodory, Helly and the others in the max-plus world
- Tropical convexity via cellular resolutions
- Title not available (Why is that?)
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- Title not available (Why is that?)
- Max-Plus Convex Geometry
Cited In (14)
- On a tropical dual Nullstellensatz
- Finitely maxitive \(T\)-conditional possibility theory: coherence and extension
- Tropical linear-fractional programming and parametric mean payoff games
- Tropical Fourier-Motzkin elimination, with an application to real-time verification
- Best approximation in max-plus semimodules
- Monomial Tropical Cones for Multicriteria Optimization
- The number of extreme points of tropical polyhedra
- Complexity of tropical and MIN-plus linear prevarieties
- Carathéodory, Helly and the others in the max-plus world
- Computing the vertices of tropical polyhedra using directed hypergraphs
- The level set method for the two-sided max-plus eigenproblem
- Face posets of tropical polyhedra and monomial ideals
- Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
- Conditional independence in max-linear Bayesian networks
Uses Software
This page was built for publication: Tropical polar cones, hypergraph transversals, and mean payoff games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q550656)
