Professor Thomas Erlebach thomas.erlebach@durham.ac.uk
Professor Computer Science
Sorting and Hypergraph Orientation under Uncertainty with Predictions
Erlebach, Thomas; de Lima, Murilo; Megow, Nicole; Schlöter, Jens
Authors
Murilo de Lima
Nicole Megow
Jens Schlöter
Abstract
Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to minimize the number of queries needed to solve a problem. We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty, assuming access to untrusted predictions for the uncertain values. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions. For sorting, our algorithm uses the optimal number of queries for accurate predictions and at most twice the optimal number for arbitrarily wrong predictions. For hypergraph orientation, for any γ ≥ 2, we give an algorithm that uses at most 1 + 1/γ times the optimal number of queries for accurate predictions and at most γ times the optimal number for arbitrarily wrong predictions. These tradeoffs are the best possible. We also consider different error metrics and show that the performance of our algorithms degrades smoothly with the prediction error in all the cases where this is possible.
Citation
Erlebach, T., de Lima, M., Megow, N., & Schlöter, J. (2023). Sorting and Hypergraph Orientation under Uncertainty with Predictions. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (5577-5585). https://doi.org/10.24963/ijcai.2023/619
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023) |
Start Date | Aug 19, 2023 |
End Date | Aug 25, 2023 |
Acceptance Date | Apr 19, 2023 |
Publication Date | 2023 |
Deposit Date | Jun 14, 2023 |
Publicly Available Date | Dec 31, 2023 |
Pages | 5577-5585 |
Book Title | Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence |
DOI | https://doi.org/10.24963/ijcai.2023/619 |
Public URL | https://durham-repository.worktribe.com/output/1134692 |
Publisher URL | https://www.ijcai.org/proceedings/2023/619 |
Files
Accepted Conference Proceeding
(272 Kb)
PDF
You might also like
Package Delivery Using Drones with Restricted Movement Areas
(2022)
Presentation / Conference Contribution
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
(2022)
Presentation / Conference Contribution
Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty
(2021)
Presentation / Conference Contribution
Parameterized temporal exploration problems
(2022)
Presentation / Conference Contribution
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search