Technical Report 2003-015

Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming

Henrik Björklund and Sven Sandberg

March 2003

The problem of maximizing functions from the boolean hypercube to real numbers arises naturally in a wide range of applications. This paper studies an even more general setting, in which the function to maximize is defined on what we call a hyperstructure. A hyperstructure is the Cartesian product of finite sets with possibly more than two elements. We also relax the codomain to any partially ordered set. Well-behaved such functions arise in game theoretic contexts, in particular from parity games (equivalent to the modal mu-calculus model checking) and simple stochastic games (Björklund, Sandberg, Vorobyov 2003). We show how several subexponential algorithms for linear programming (Kalai 1992, Matousek, Sharir, Welzl 1992) can be adapted to hyperstructures and give a reduction to the abstract optimization problems introduced in (Gärtner1995).

Available as Postscript (745 kB) and compressed Postscript (262 kB)

Download BibTeX entry.