1 Search Results for "Lavastida, Thomas"

Document
DOI: 10.4230/LIPIcs.ESA.2021.59
Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing

Authors: Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We propose a new model for augmenting algorithms with predictions by requiring that they are formally learnable and instance robust. Learnability ensures that predictions can be efficiently constructed from a reasonable amount of past data. Instance robustness ensures that the prediction is robust to modest changes in the problem input, where the measure of the change may be problem specific. Instance robustness insists on a smooth degradation in performance as a function of the change. Ideally, the performance is never worse than worst-case bounds. This also allows predictions to be objectively compared. We design online algorithms with predictions for a network flow allocation problem and restricted assignment makespan minimization. For both problems, two key properties are established: high quality predictions can be learned from a small sample of prior instances and these predictions are robust to errors that smoothly degrade as the underlying problem instance changes.
Cite as

Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lavastida_et_al:LIPIcs.ESA.2021.59,
  author =	{Lavastida, Thomas and Moseley, Benjamin and Ravi, R. and Xu, Chenyang},
  title =	{{Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.59},
  URN =		{urn:nbn:de:0030-drops-146405},
  doi =		{10.4230/LIPIcs.ESA.2021.59},
  annote =	{Keywords: Learning-augmented algorithms, Online algorithms, Flow allocation}
}
  • Refine by Author
  • 1 Lavastida, Thomas
  • 1 Moseley, Benjamin
  • 1 Ravi, R.
  • 1 Xu, Chenyang

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Flow allocation
  • 1 Learning-augmented algorithms
  • 1 Online algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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