Cyclic games and linear programming |
| |
Authors: | Sergei Vorobyov |
| |
Institution: | Institut für Informationssysteme, Abteilung für Datenbanken und Artificial Intelligence, Technische Universität Wien, Favoritenstraße 9, A-1040 Wien, Austria |
| |
Abstract: | New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem in NP ∩ coNP, based on linear programming (LP), LP-representations, combinatorial LP, linear complementarity problem (LCP), controlled LP are surveyed. |
| |
Keywords: | Mean payoff Simple stochastic Parity Discounted payoff games Longest-shortest paths Generalized linear complementarity Controlled linear programming Combinatorial linear programming Subexponential algorithms Iterative improvement Local search |
本文献已被 ScienceDirect 等数据库收录! |
|