Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910329353535488 |
|---|---|
| author | Kevi, Eniko Thang, Nguyen Kim |
| author_facet | Kevi, Eniko Thang, Nguyen Kim |
| contents | Matching problems have been widely studied in the research community, especially Ad-Auctions with many applications ranging from network design to advertising. Following the various advancements in machine learning, one natural question is whether classical algorithms can benefit from machine learning and obtain better-quality solutions. Even a small percentage of performance improvement in matching problems could result in significant gains for the studied use cases. For example, the network throughput or the revenue of Ad-Auctions can increase remarkably. This paper presents algorithms with machine learning predictions for the Online Bounded Allocation and the Online Ad-Auctions problems. We constructed primal-dual algorithms that achieve competitive performance depending on the quality of the predictions. When the predictions are accurate, the algorithms' performance surpasses previous performance bounds, while when the predictions are misleading, the algorithms maintain standard worst-case performance guarantees. We provide supporting experiments on generated data for our theoretical findings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08701 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems Kevi, Eniko Thang, Nguyen Kim Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory Machine Learning Matching problems have been widely studied in the research community, especially Ad-Auctions with many applications ranging from network design to advertising. Following the various advancements in machine learning, one natural question is whether classical algorithms can benefit from machine learning and obtain better-quality solutions. Even a small percentage of performance improvement in matching problems could result in significant gains for the studied use cases. For example, the network throughput or the revenue of Ad-Auctions can increase remarkably. This paper presents algorithms with machine learning predictions for the Online Bounded Allocation and the Online Ad-Auctions problems. We constructed primal-dual algorithms that achieve competitive performance depending on the quality of the predictions. When the predictions are accurate, the algorithms' performance surpasses previous performance bounds, while when the predictions are misleading, the algorithms maintain standard worst-case performance guarantees. We provide supporting experiments on generated data for our theoretical findings. |
| title | Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems |
| topic | Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2402.08701 |