Deterministic sub-exponential algorithm for discounted-sum games with unary weights

DOI10.1145/3661814.3662080MaRDI QIDQ6970278zbMATH OpenFDO

Authors Ali Naghash Asadi, Krishnendu Chatterjee, Jakub Svoboda, Raimundo Saona Urmeneta

Publication date 18 June 2025

Full work available at URL https://doi.org/10.1145/3661814.3662080

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43)

Cites work

• A Deterministic Subexponential Algorithm for Solving Parity Games
• A faster deterministic exponential time algorithm for energy games and mean payoff games
• A reduction from parity games to simple stochastic games
• A subexponential randomized algorithm for the simple stochastic game problem
• Alternation
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Deciding Parity Games in Quasi-polynomial Time
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
• Faster algorithms for mean-payoff games
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 2038772 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 7788375 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Littlewood-Type Problems on [0,1]
• On satisficing in quantitative games
• Positional strategies for mean payoff games
• Quantitative interprocedural analysis
• Solving Parity Games in Big Steps
• Stochastic Games
• Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• The complexity of mean payoff games on graphs
• The complexity of solving stochastic games on graphs
• The complexity of stochastic games
• The complexity of the simplex method

Cited in

(1)

• Discounted-sum automata with multiple discount factors

This page was built for publication: Deterministic sub-exponential algorithm for discounted-sum games with unary weights

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970278)