Combinatorial Simplex Algorithms Can Solve Mean Payoff Games

DOI10.1137/140953800zbMath1336.90057arXiv1309.5925OpenAlexW4300321013WikidataQ117245052 ScholiaQ117245052MaRDI QIDQ5245379

Michael Joswig, Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert

Publication date: 8 April 2015

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingtropical geometryreal closed fieldsmean payoff gamessymbolic perturbationHahn series

Mathematics Subject Classification ID

Linear programming (90C05) Games with infinitely many players (91A07) Applications of model theory (03C98)

Related Items

Tropicalization of facets of polytopes, Abstract tropical linear programming, The polyhedral geometry of truthful auctions, Computing tropical varieties over fields with valuation, Convergent Hahn series and tropical geometry of higher rank, Solving mean-payoff games via quasi dominions, Tropical linear spaces and tropical convexity, Constraint Satisfaction Problems over Numeric Domains, What Tropical Geometry Tells Us about the Complexity of Linear Programming, Computing tropical points and tropical links, Solving Mean-Payoff Games via Quasi Dominions, Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games, A strongly polynomial method for solving integer max-linear optimization problems in a generic case