Cyclic games and linear programming
New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem inNP? ? coNP, based on linear programming (LP), LP-representations, combinatorial LP, linear complementarity problem (LCP), controlled LP are surveyed.
mean payoff simple stochastic parity discounted payoff games longestshortest paths generalized linear complementarity controlled linear programming combinatorial linear programming subexponential algorithms iterative improvement local search