Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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 > 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:
DateEvent
20 June 2015Published
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us