Tropical polar cones, hypergraph transversals, and mean payoff games

DOI10.1016/J.LAA.2011.02.004MaRDI QIDQ550656zbMATH OpenOpenAlexFDO

Authors Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz

Publication date 13 July 2011

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2778

zbMATH Keywords

polyhedratropical convexityminimal solutionshypergraph transversalsmax-plus convexitymax-plus semiringminimal hitting sets

Mathematics Subject Classification ID

Max-plus and related algebras (15A80) Semirings (16Y60) Axiomatic and generalized convexity (52A01)

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.

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

Cites work

• scientific article; zbMATH DE number 426216 (Why is no real title available?)
• scientific article; zbMATH DE number 3869093 (Why is no real title available?)
• scientific article; zbMATH DE number 4081342 (Why is no real title available?)
• scientific article; zbMATH DE number 3570223 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 2221682 (Why is no real title available?)
• -convexity
• A constructive fixed point theorem for min-max functions
• A note on systems with max-min and max-product constraints
• Affine Buildings and Tropical Convexity
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Carathéodory, Helly and the others in the max-plus world
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Duality and separation theorems in idempotent semimodules.
• Generators, extremals and bases of max cones
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• Idempotent functional analysis: An algebraic approach
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• Max-Plus Convex Geometry
• Minimal half-spaces and external representation of tropical polyhedra
• Minimax algebra
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• STACS 97. 14th annual symposium on theoretical aspects of computer science. Lübeck, Germany, February 27 -- March 1, 1997. Proceedings
• Scheduling with AND/OR Precedence Constraints
• Shelling polyhedral 3-balls and 4-polytopes
• Stochastic Games with Perfect Information and Time Average Payoff
• The Max-Atom Problem and Its Relevance
• The Minkowski theorem for max-plus convex sets
• The Perron-Frobenius theorem for homogeneous, monotone functions
• The complexity of mean payoff games on graphs
• The duality theorem for min-max functions
• The maximum numbers of faces of a convex polytope
• The number of extreme points of tropical polyhedra
• The tropical analogue of polar cones
• The tropical double description method
• Tropical Convex Hull Computations
• Tropical convexity
• Tropical convexity via cellular resolutions
• Tropical halfspaces
• Tropical polyhedra are equivalent to mean payoff games

Cited in

(17)

• Computing the vertices of tropical polyhedra using directed hypergraphs
• Tropical linear-fractional programming and parametric mean payoff games
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Monomial Tropical Cones for Multicriteria Optimization
• On a tropical dual Nullstellensatz
• Tropical polyhedra are equivalent to mean payoff games
• The number of extreme points of tropical polyhedra
• The level set method for the two-sided max-plus eigenproblem
• Finitely maxitive \(T\)-conditional possibility theory: coherence and extension
• Complexity of tropical and MIN-plus linear prevarieties
• Best approximation in max-plus semimodules
• Face posets of tropical polyhedra and monomial ideals
• Conditional independence in max-linear Bayesian networks
• Carathéodory, Helly and the others in the max-plus world
• The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• The tropical analogue of polar cones

Describes a project that uses

Uses Software

• TPLib

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)