DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2022.99

Double Coverage with Machine-Learned Advice

Authors: Alexander Lindermayr, Nicole Megow, and Bertrand Simon

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

We study the fundamental online k-server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence, we assume that there is given some advice (e.g. machine-learned predictions) on an algorithm’s decision. There is, however, no guarantee on the quality of the prediction and it might be far from being correct. Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for k-server on the line (Chrobak et al., SIDMA 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent competitive ratio, which is a function of a user-defined confidence parameter, and which interpolates smoothly between an optimal consistency, the performance in case that all predictions are correct, and the best-possible robustness regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff, within a class of deterministic algorithms respecting local and memoryless properties. Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is remarkable that the previous algorithm crucially exploits memory, whereas our algorithm is memoryless. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.

Cite as

Alexander Lindermayr, Nicole Megow, and Bertrand Simon. Double Coverage with Machine-Learned Advice. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 99:1-99:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lindermayr_et_al:LIPIcs.ITCS.2022.99,
  author =	{Lindermayr, Alexander and Megow, Nicole and Simon, Bertrand},
  title =	{{Double Coverage with Machine-Learned Advice}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{99:1--99:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.99},
  URN =		{urn:nbn:de:0030-drops-156954},
  doi =		{10.4230/LIPIcs.ITCS.2022.99},
  annote =	{Keywords: online k-server problem, competitive analysis, learning-augmented algorithms, untrusted predictions, consistency, robustness}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2020.65

Elimination Distance to Bounded Degree on Planar Graphs

Authors: Alexander Lindermayr, Sebastian Siebertz, and Alexandre Vigny

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph G and integers d and k decides in time f(k,d)⋅ n^c for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most k.

Cite as

Alexander Lindermayr, Sebastian Siebertz, and Alexandre Vigny. Elimination Distance to Bounded Degree on Planar Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 65:1-65:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lindermayr_et_al:LIPIcs.MFCS.2020.65,
  author =	{Lindermayr, Alexander and Siebertz, Sebastian and Vigny, Alexandre},
  title =	{{Elimination Distance to Bounded Degree on Planar Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{65:1--65:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.65},
  URN =		{urn:nbn:de:0030-drops-127557},
  doi =		{10.4230/LIPIcs.MFCS.2020.65},
  annote =	{Keywords: Elimination distance, parameterized complexity, structural graph theory}
}

Search Results

Documents authored by Lindermayr, Alexander

Double Coverage with Machine-Learned Advice

Abstract

Cite as

Elimination Distance to Bounded Degree on Planar Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message