id:"swepub:oai:DiVA.org:uu-72104"
Search: id:"swepub:oai:DiVA.org:uu-72104" > Randomized Subexpon...
- 1 of 1
- Previous record
- Next record
- To hitlist
Randomized Subexponential Algorithms for Infinite Games
-
- Björklund, Henrik (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,datalogi
-
- Sandberg, Sven (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,datalogi
-
- Vorobyov, Sergei (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi
- (creator_code:org_t)
- Uppsala Universitet, 2004
- English.
- Series: Technical report / Department of Information Technology, Uppsala University, 1404-3203 ; 2004-011
- Reports (other academic/artistic)
Abstract
Subject headings
Close
- The complexity of solving infinite games, including parity, mean payoff, and simple stochastic games, is an important open problem in verification, automata theory, and complexity theory. In this paper we develop an abstract setting for studying and solving such games, as well as related problems, based on function optimization over certain discrete structures. We introduce new classes of completely local-global (CLG) and recursively local-global (RLG) functions, and show that strategy evaluation functions for parity and simple stochastic games belong to these classes. We also establish a relation to the previously well-studied completely unimodal (CU) and local-global functions. A number of nice properties of CLG-functions are proved. In this setting, we survey several randomized optimization algorithms appropriate for CU-, CLG-, and RLG-functions. We show that the subexponential algorithms for linear programming by Kalai and Matousek, Sharir, and Welzl, can be adapted to optimizing the functions we study, with preserved subexponential expected running time. We examine the relations to two other abstract frameworks for subexponential optimization, the LP-type problems of Matousek, Sharir, Welzl, and the abstract optimization problems of Gärtner. The applicability of our abstract optimization approach to parity games builds upon a discrete strategy evaluation measure. We also consider local search type algorithms, and settle two nontrivial, but still exponential, upper bounds. As applications we address some complexity-theoretic issues including non-PLS-completeness of the problems studied.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Computer science
- Datalogi
Publication and Content Type
- vet (subject category)
- rap (subject category)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Björklund, Henri ...
- Sandberg, Sven
- Vorobyov, Sergei
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Parts in the series
- Technical report ...
- By the university
- Uppsala University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
