The Pareto Frontier of Randomized Learning-Augmented Online Bidding
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918500569710592 |
|---|---|
| author | Degryse, Mathis Saakour, Imrane Dürr, Christoph Angelopoulos, Spyros |
| author_facet | Degryse, Mathis Saakour, Imrane Dürr, Christoph Angelopoulos, Spyros |
| contents | Online bidding is a classical problem in online decision-making, with applications in resource allocation, hierarchical clustering, and the analysis of approximation algorithms. We study its randomized learning-augmented variant, where an online algorithm generates a sequence of random bids while leveraging predictions from an oracle. We provide analytical upper and lower bounds on the optimal consistency $C$ as a function of the robustness $R$, which match when $R \geq 2.885$, effectively closing the gap left by previous work. The key technical ingredient is the notion of a bidding function, a novel abstraction that provides a unified framework for the design and analysis of randomized bidding strategies. We complement our theoretical results with an experimental application of randomized bidding to the incremental median problem, demonstrating the applicability of our algorithm in practical clustering settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06106 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Pareto Frontier of Randomized Learning-Augmented Online Bidding Degryse, Mathis Saakour, Imrane Dürr, Christoph Angelopoulos, Spyros Data Structures and Algorithms F.2.0 Online bidding is a classical problem in online decision-making, with applications in resource allocation, hierarchical clustering, and the analysis of approximation algorithms. We study its randomized learning-augmented variant, where an online algorithm generates a sequence of random bids while leveraging predictions from an oracle. We provide analytical upper and lower bounds on the optimal consistency $C$ as a function of the robustness $R$, which match when $R \geq 2.885$, effectively closing the gap left by previous work. The key technical ingredient is the notion of a bidding function, a novel abstraction that provides a unified framework for the design and analysis of randomized bidding strategies. We complement our theoretical results with an experimental application of randomized bidding to the incremental median problem, demonstrating the applicability of our algorithm in practical clustering settings. |
| title | The Pareto Frontier of Randomized Learning-Augmented Online Bidding |
| topic | Data Structures and Algorithms F.2.0 |
| url | https://arxiv.org/abs/2605.06106 |