Abstract
We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online graph problems. The measure captures errors due to absent predicted requests as well as unpredicted actual requests; hence, predicted and actual inputs can be of arbitrary size. We achieve refined performance guarantees for previously studied network design problems in the online-list model, such as Steiner tree and facility location. Further, we initiate the study of learning-augmented algorithms for online routing problems, such as the online traveling salesperson problem and the online dial-a-ride problem, where (transportation) requests arrive over time (online-time model). We provide a general algorithmic framework and we give error-dependent performance bounds that improve upon known worst-case barriers, when given accurate predictions, at the cost of slightly increased worst-case bounds when given predictions of arbitrary quality.
| Original language | English |
|---|---|
| Title of host publication | Advances in Neural Information Processing Systems 35 (NeurIPS 2022) |
| Subtitle of host publication | [Proceedings] |
| Editors | S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh |
| Publisher | Neural information processing systems foundation |
| Pages | 1-13 |
| Number of pages | 13 |
| ISBN (Electronic) | 9781713871088 |
| Publication status | Published - 2022 |
| Event | 36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans, United States Duration: 28 Nov 2022 → 9 Dec 2022 |
Publication series
| Name | NeurIPS Proceedings |
|---|
Conference
| Conference | 36th Conference on Neural Information Processing Systems, NeurIPS 2022 |
|---|---|
| Country/Territory | United States |
| City | New Orleans |
| Period | 28/11/22 → 9/12/22 |
Bibliographical note
Funding Information:The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 “Optimization for and with Machine Learning (OPTIMAL)” and Gravitation-grant NETWORKS-024.002.003; the German Science Foundation (DFG) under contract 146371743 – TRR 89 Invasive Computing; the ERC Advanced Grant 788893 AMDROMA “Algorithmic and Mechanism Design Research in Online Markets”; the MIUR - PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets”; and the MUR - FSE REACT EU - PON R&I 2014-2020.
Publisher Copyright:
© 2022 Neural information processing systems foundation. All rights reserved.
Funding
The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 “Optimization for and with Machine Learning (OPTIMAL)” and Gravitation-grant NETWORKS-024.002.003; the German Science Foundation (DFG) under contract 146371743 – TRR 89 Invasive Computing; the ERC Advanced Grant 788893 AMDROMA “Algorithmic and Mechanism Design Research in Online Markets”; the MIUR - PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets”; and the MUR - FSE REACT EU - PON R&I 2014-2020.