DROPS

Document

Scheduling (Dagstuhl Seminar 25121)

Authors: Claire Mathieu, Nicole Megow, Benjamin J. Moseley, Frits C. R. Spieksma, and Alexander Lindermayr

Published in: Dagstuhl Reports, Volume 15, Issue 3 (2025)

Abstract

This report documents the program and outcomes of Dagstuhl Seminar 25121, "Scheduling". The seminar focused on bridging traditional algorithmic scheduling with the emerging field of fairness in resource allocation. Scheduling is a longstanding research area that has been studied from both practical and theoretical perspectives in computer science, mathematical optimization, and operations research for over 70 years. Fairness has become a key concern in recent years, particularly in the context of resource allocation and scheduling, where it naturally arises in applications such as kidney exchange, school choice, and political districting. The seminar centered on three main themes: (1) fair allocation, (2) fairness versus quality of service, and (3) modeling aspects of fairness in scheduling.

Cite as

Claire Mathieu, Nicole Megow, Benjamin J. Moseley, Frits C. R. Spieksma, and Alexander Lindermayr. Scheduling (Dagstuhl Seminar 25121). In Dagstuhl Reports, Volume 15, Issue 3, pp. 94-112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{mathieu_et_al:DagRep.15.3.94,
  author =	{Mathieu, Claire and Megow, Nicole and Moseley, Benjamin J. and Spieksma, Frits C. R. and Lindermayr, Alexander},
  title =	{{Scheduling (Dagstuhl Seminar 25121)}},
  pages =	{94--112},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{3},
  editor =	{Mathieu, Claire and Megow, Nicole and Moseley, Benjamin J. and Spieksma, Frits C. R. and Lindermayr, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.3.94},
  URN =		{urn:nbn:de:0030-drops-248981},
  doi =		{10.4230/DagRep.15.3.94},
  annote =	{Keywords: scheduling, fairness, mathematical optimization, algorithms and complexity, uncertainty}
}

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

Scheduling (Dagstuhl Seminar 25121)

Abstract

Cite as

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