@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).}
}