Sökning: id:"swepub:oai:DiVA.org:uu-49008" >
Algorithms for Comb...
Algorithms for Combinatorial Optimization and Games Adapted from Linear Programming
-
- Björklund, Henrik (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
- Sandberg, Sven (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
(creator_code:org_t)
- Uppsala: Department of Information Technology, Uppsala University, 2003
- Engelska.
-
Serie: Technical report / Department of Information Technology, Uppsala University, 1404-3203 ; 2003-015
- Relaterad länk:
-
http://www.it.uu.se/...
-
visa fler...
-
https://uu.diva-port... (primary) (Raw object)
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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)