Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2505.04949 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912575237652480 |
|---|---|
| author | Canonne, Clément L. Chen, Kenny Mestre, Julián |
| author_facet | Canonne, Clément L. Chen, Kenny Mestre, Julián |
| contents | We study online algorithms with predictions using distributional advice, a type of prediction that arises when leveraging expert knowledge or historical data. To demonstrate the usefulness and versatility of this framework, we focus on the fundamental problem of online metric matching, considering both the fractional and integral variants. Our main positive result is, for the former, an algorithm achieving the optimal cost under perfect advice, while smoothly defaulting to competitive ratios comparable to advice-free algorithms as the prediction's quality degrades. For the integral matching, we are able to provide an algorithm with essentially the same guarantees, up to an additive sublinear term. We conclude by discussing how our algorithmic framework can be extended to other online optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04949 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design Canonne, Clément L. Chen, Kenny Mestre, Julián Data Structures and Algorithms We study online algorithms with predictions using distributional advice, a type of prediction that arises when leveraging expert knowledge or historical data. To demonstrate the usefulness and versatility of this framework, we focus on the fundamental problem of online metric matching, considering both the fractional and integral variants. Our main positive result is, for the former, an algorithm achieving the optimal cost under perfect advice, while smoothly defaulting to competitive ratios comparable to advice-free algorithms as the prediction's quality degrades. For the integral matching, we are able to provide an algorithm with essentially the same guarantees, up to an additive sublinear term. We conclude by discussing how our algorithmic framework can be extended to other online optimization problems. |
| title | With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.04949 |