Sökning: onr:"swepub:oai:DiVA.org:uu-49009" >
On Combinatorial St...
On Combinatorial Structure and Algorithms for Parity Games
-
- 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
-
- Vorobyov, Sergei (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-002
- Relaterad länk:
-
https://uu.diva-port... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- In this paper we identify and systematically explore the combinatorial structure underlying parity and simple stochastic games. We introduce the class of Completely LG (local-global) functions with nice structural properties pertinent to games and allowing for efficient optimization by iterative improvement local search style algorithms. We demonstrate several important combinatorial properties of Completely LG functions, allowing for many optimization algorithms, and establish a relation with the subclass of Completely Unimodal functions, studied by Hammer et al. [1988] Williamson Hoke [1988], and Wiedemann [1985]. We also describe a new, compared to our recent [STACS'2003], subexponential randomized algorithm for CU-functions, CLG-functions, parity, and simple stochastic games, and establish a relation with the class of LP-type problems introduced and investigated by Sharir \& Welzl [1992] and Matousek, Sharir \& Welzl [1992].
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publikations- och innehållstyp
- vet (ämneskategori)
- rap (ämneskategori)