Polynomial-time algorithms for energy games with special weight structures

DOI10.1007/s00453-013-9843-7zbMath1303.91048arXiv1604.08234OpenAlexW106665802MaRDI QIDQ487011

Danupon Nanongkai, Sebastian Krinninger, Krishnendu Chatterjee, Monika R. Henzinger

Publication date: 19 January 2015

Published in: Algorithmica, Algorithms – ESA 2012 (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmspolynomial-time algorithmsenergy gamesmean-payoff gamesturn-based infinite duration games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) 2-person games (91A05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (11)

The Complexity of Infinitely Repeated Alternating Move Games ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Automated competitive analysis of real-time scheduling with graph games ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ Checking dynamic consistency of conditional hyper temporal networks via mean payoff games. Hardness and (pseudo) singly-exponential time algorithm ⋮ On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost ⋮ A note on the approximation of mean-payoff games ⋮ Unnamed Item ⋮ The complexity of multi-mean-payoff and multi-energy games ⋮ Looking at mean-payoff and total-payoff through windows

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• On canonical forms for zero-sum stochastic mean payoff games
• Faster algorithms for mean-payoff games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Cyclic games and linear programming
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Borel determinacy
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Linear programming, the simplex algorithm and simple polytopes
• A subexponential bound for linear programming
• Upper bounds to the clique width of graphs
• Effectively solvable classes of cyclical games
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Mean Cost Cyclical Games
• A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
• Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Clique-Width and Parity Games
• Better Quality in Synthesis through Quantitative Objectives
• A combinatorial bound for linear programming and related problems
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

This page was built for publication: Polynomial-time algorithms for energy games with special weight structures