The Library
Fixed-dimensional energy games are in pseudo-polynomial time
Tools
Tools
Tools
Jurdzinski, Marcin, Lazic, Ranko and Schmitz, Sylvain (2015) Fixed-dimensional energy games are in pseudo-polynomial time. In: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, 9135 pp. 260-272. ISBN 9783662476659. ISSN 0302-9743. doi:10.1007/978-3-662-47666-6_21
|
PDF
WRAP_0070379-cs-240615-lncs.pdf - Accepted Version - Requires a PDF viewer. Download (482Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-47666-6_21
Abstract
We generalise the hyperplane separation technique (Chatterjee and Velner, 2013) from multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the latter whose running time is exponential only in the dimension, but not in the number of vertices of the game graph. This answers an open question whether energy games with arbitrary initial credit can be solved in pseudo-polynomial time for fixed dimensions 3 or larger (Chaloupka, 2013). It also improves the complexity of solving multi-dimensional energy games with given initial credit from non-elementary (Brázdil, Jančar, and Kučera, 2010) to 2EXPTIME, thus establishing their 2EXPTIME-completeness.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Game theory | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Journal or Publication Title: | Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II | ||||
| Publisher: | Springer Verlag | ||||
| Place of Publication: | Berlin ; Heidelberg | ||||
| ISBN: | 9783662476659 | ||||
| ISSN: | 0302-9743 | ||||
| Editor: | Halldórsson , Magnús M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina | ||||
| Official Date: | 20 June 2015 | ||||
| Dates: |
|
||||
| Volume: | 9135 | ||||
| Number of Pages: | 13 | ||||
| Page Range: | pp. 260-272 | ||||
| DOI: | 10.1007/978-3-662-47666-6_21 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Funder: | France. Agence nationale de la recherche (ANR), Leverhulme Trust (LT), Engineering and Physical Sciences Research Council (EPSRC) | ||||
| Grant number: | 11-BS02-001-01 (ANR) ; VP1-2014-041 (LT) ; EP/M011801/1 (EPSRC) | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 42nd International Colloquium, ICALP 2015 | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Kyoto, Japan | ||||
| Date(s) of Event: | 6-10 Jul 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
