@TechReport{ it:2003-015,
author = {Henrik Bj{\"o}rklund and Sven Sandberg},
title = {Algorithms for Combinatorial Optimization and Games
Adapted from Linear Programming},
institution = {Department of Information Technology, Uppsala University},
department = {Computing Science Division},
year = {2003},
number = {2003-015},
month = mar,
abstract = {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{\"o}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{\"a}rtner1995).}
}