Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming

• 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).

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Publikations- och innehållstyp

vet (ämneskategori)

rap (ämneskategori)