Primal-Dual Algorithms with Predictions for Online Bounded Allocation
  and Ad-Auctions Problems
Eniko Kevi Nguyen Kim Thang
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.