Tropical polar cones, hypergraph transversals, and mean payoff games

DOI10.1016/j.laa.2011.02.004zbMath1217.14047arXiv1004.2778OpenAlexW1821883734MaRDI QIDQ550656

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)

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

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

Related Items

The level set method for the two-sided max-plus eigenproblem ⋮ Tropical Fourier–Motzkin elimination, with an application to real-time verification ⋮ The number of extreme points of tropical polyhedra ⋮ Computing the vertices of tropical polyhedra using directed hypergraphs ⋮ Monomial Tropical Cones for Multicriteria Optimization ⋮ Face posets of tropical polyhedra and monomial ideals ⋮ Tropical linear-fractional programming and parametric mean payoff games ⋮ Best approximation in max-plus semimodules ⋮ Complexity of tropical and MIN-plus linear prevarieties ⋮ Finitely maxitive \(T\)-conditional possibility theory: coherence and extension ⋮ Conditional independence in max-linear Bayesian networks

Uses Software

• TPLib

Cites Work

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