4 Search Results for "Allamigeon, Xavier"

Document
DOI: 10.4230/LIPIcs.MFCS.2022.63
Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees

Authors: Zhuan Khye Koh and Georg Loho

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Parity games have witnessed several new quasi-polynomial algorithms since the breakthrough result of Calude et al. (STOC 2017). The combinatorial object underlying these approaches is a universal tree, as identified by Czerwiński et al. (SODA 2019). By proving a quasi-polynomial lower bound on the size of a universal tree, they have highlighted a barrier that must be overcome by all existing approaches to attain polynomial running time. This is due to the existence of worst case instances which force these algorithms to explore a large portion of the tree. As an attempt to overcome this barrier, we propose a strategy iteration framework which can be applied on any universal tree. It is at least as fast as its value iteration counterparts, while allowing one to take bigger leaps in the universal tree. Our main technical contribution is an efficient method for computing the least fixed point of 1-player games. This is achieved via a careful adaptation of shortest path algorithms to the setting of ordered trees. By plugging in the universal tree of Jurdziński and Lazić (LICS 2017), or the Strahler universal tree of Daviaud et al. (ICALP 2020), we obtain instantiations of the general framework that take time O(mn²log nlog d) and O(mn²log³ n log d) respectively per iteration.
Cite as

Zhuan Khye Koh and Georg Loho. Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{koh_et_al:LIPIcs.MFCS.2022.63,
  author =	{Koh, Zhuan Khye and Loho, Georg},
  title =	{{Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.63},
  URN =		{urn:nbn:de:0030-drops-168619},
  doi =		{10.4230/LIPIcs.MFCS.2022.63},
  annote =	{Keywords: parity games, strategy iteration, value iteration, progress measure, universal trees}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.110
Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games

Authors: Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz, and Mateusz Skomra

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on an oracle, evaluating the dynamic programming operator up to a given precision. We show that the number of calls to the oracle needed to determine exact optimal (positional) strategies is, up to a factor polynomial in the dimension, of order R/sep, where the "separation" sep is defined as the minimal difference between distinct values arising from strategies, and R is a metric estimate, involving the norm of approximate sub and super-eigenvectors of the dynamic programming operator. We illustrate this method by two applications. The first one is a new proof, leading to improved complexity estimates, of a theorem of Boros, Elbassioni, Gurvich and Makino, showing that turn-based mean payoff games with a fixed number of random positions can be solved in pseudo-polynomial time. The second one concerns entropy games, a model introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. The rank of an entropy game is defined as the maximal rank among all the ambiguity matrices determined by strategies of the two players. We show that entropy games with a fixed rank, in their original formulation, can be solved in polynomial time, and that an extension of entropy games incorporating weights can be solved in pseudo-polynomial time under the same fixed rank condition.
Cite as

Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz, and Mateusz Skomra. Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 110:1-110:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{allamigeon_et_al:LIPIcs.ICALP.2022.110,
  author =	{Allamigeon, Xavier and Gaubert, St\'{e}phane and Katz, Ricardo D. and Skomra, Mateusz},
  title =	{{Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{110:1--110:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.110},
  URN =		{urn:nbn:de:0030-drops-164511},
  doi =		{10.4230/LIPIcs.ICALP.2022.110},
  annote =	{Keywords: Mean-payoff games, entropy games, value iteration, Perron root, separation bounds, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.24
Signed Tropical Convexity

Authors: Georg Loho and László A. Végh

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas' lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.
Cite as

Georg Loho and László A. Végh. Signed Tropical Convexity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 24:1-24:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{loho_et_al:LIPIcs.ITCS.2020.24,
  author =	{Loho, Georg and V\'{e}gh, L\'{a}szl\'{o} A.},
  title =	{{Signed Tropical Convexity}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{24:1--24:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.24},
  URN =		{urn:nbn:de:0030-drops-117097},
  doi =		{10.4230/LIPIcs.ITCS.2020.24},
  annote =	{Keywords: tropical convexity, signed tropical numbers, Farkas' lemma}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2443
The Tropical Double Description Method

Authors: Xavier Allamigeon, Stéphane Gaubert, and Éric Goubault

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We develop a tropical analogue of the classical double description method allowing one to compute an internal representation (in terms of vertices) of a polyhedron defined externally (by inequalities). The heart of the tropical algorithm is a characterization of the extreme points of a polyhedron in terms of a system of constraints which define it. We show that checking the extremality of a point reduces to checking whether there is only one minimal strongly connected component in an hypergraph. The latter problem can be solved in almost linear time, which allows us to eliminate quickly redundant generators. We report extensive tests (including benchmarks from an application to static analysis) showing that the method outperforms experimentally the previous ones by orders of magnitude. The present tools also lead to worst case bounds which improve the ones provided by previous methods.
Cite as

Xavier Allamigeon, Stéphane Gaubert, and Éric Goubault. The Tropical Double Description Method. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 47-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{allamigeon_et_al:LIPIcs.STACS.2010.2443,
  author =	{Allamigeon, Xavier and Gaubert, St\'{e}phane and Goubault, \'{E}ric},
  title =	{{The Tropical Double Description Method}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{47--58},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2443},
  URN =		{urn:nbn:de:0030-drops-24435},
  doi =		{10.4230/LIPIcs.STACS.2010.2443},
  annote =	{Keywords: Convexity in tropical algebra, algorithmics and combinatorics of tropical polyhedra, computational geometry, discrete event systems, static analysis}
}
  • Refine by Author
  • 2 Allamigeon, Xavier
  • 2 Gaubert, Stéphane
  • 2 Loho, Georg
  • 1 Goubault, Éric
  • 1 Katz, Ricardo D.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 2 value iteration
  • 1 Convexity in tropical algebra
  • 1 Farkas' lemma
  • 1 Mean-payoff games
  • 1 Perron root
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2022
  • 1 2010
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact