License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.114
URN: urn:nbn:de:0030-drops-106909
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10690/
Go to the corresponding LIPIcs Volume Portal

Dorfman, Dani ; Kaplan, Haim ; Zwick, Uri

A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games

pdf-format:
LIPIcs-ICALP-2019-114.pdf (0.6 MB)

Abstract

We present an improved exponential time algorithm for Energy Games, and hence also for Mean Payoff Games. The running time of the new algorithm is O (min(m n W, m n 2^{n/2} log W)), where n is the number of vertices, m is the number of edges, and when the edge weights are integers of absolute value at most W. For small values of W, the algorithm matches the performance of the pseudopolynomial time algorithm of Brim et al. on which it is based. For W >= n2^{n/2}, the new algorithm is faster than the algorithm of Brim et al. and is currently the fastest deterministic algorithm for Energy Games and Mean Payoff Games. The new algorithm is obtained by introducing a technique of forecasting repetitive actions performed by the algorithm of Brim et al., along with the use of an edge-weight scaling technique.

BibTeX - Entry

@InProceedings{dorfman_et_al:LIPIcs:2019:10690,
  author =	{Dani Dorfman and Haim Kaplan and Uri Zwick},
  title =	{{A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{114:1--114:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10690},
  URN =		{urn:nbn:de:0030-drops-106909},
  doi =		{10.4230/LIPIcs.ICALP.2019.114},
  annote =	{Keywords: Energy Games, Mean Payoff Games, Scaling}
}

Keywords: Energy Games, Mean Payoff Games, Scaling
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI