@inproceedings{98d32e866df94dcf95bb0d8d7f0cebe6,
title = "Learning from a Sample in Online Algorithms",
abstract = "We consider three central problems in optimization: the restricted assignment load-balancing problem, the Steiner tree network design problem, and facility location clustering. We consider the online setting, where the input arrives over time, and irrevocable decisions must be made without knowledge of the future. For all these problems, any online algorithm must incur a cost that is approximately log |I| times the optimal cost in the worst-case, where |I| is the length of the input. But can we go beyond the worst-case? In this work we give algorithms that perform substantially better when a p-fraction of the input is given as a sample: the algorithm use this sample to learn a good strategy to use for the rest of the input.",
author = "Argue, {C. J.} and Frieze, {Alan M.} and Anupam Gupta and Christopher Seiler",
note = "Publisher Copyright: {\textcopyright} 2022 Neural information processing systems foundation. All rights reserved.; 36th Conference on Neural Information Processing Systems, NeurIPS 2022 ; Conference date: 28-11-2022 Through 09-12-2022",
year = "2022",
language = "English (US)",
series = "Advances in Neural Information Processing Systems",
publisher = "Neural information processing systems foundation",
editor = "S. Koyejo and S. Mohamed and A. Agarwal and D. Belgrave and K. Cho and A. Oh",
booktitle = "Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022",
}