Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)

Authors Yiding Feng, Rad Niazadeh



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.88.pdf
  • Filesize: 208 kB
  • 1 pages

Document Identifiers

Author Details

Yiding Feng
  • Department of Computer Science, Northwestern University, Evanston, IL, USA
Rad Niazadeh
  • Chicago Booth School of Business, University of Chicago, Chicago, IL, USA

Acknowledgements

The authors would like to thank Yeganeh Alimohammadi for participating in the early stages of this project, and to Amin Saberi for helpful discussions regarding the presentation of this work.

Cite AsGet BibTex

Yiding Feng and Rad Niazadeh. Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, p. 88:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.88

Abstract

In several applications of real-time matching of demand to supply in online marketplaces, the platform can allow for some latency to batch the demand and improve the matching’s efficiency. Motivated by these scenarios, we study the optimal trade-off between batching and inefficiency in online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems, where online vertices arrive in K batches. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratios known for the online variant of these problems [Mehta et al., 2007; Aggarwal et al., 2011]. Our main technique is using a family of convex-programming based matchings that distribute the demand in a particularly balanced way among supply in different stages. More precisely, we identify a sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers of the optimal matching linear program to form this family. By providing structural decompositions of the underlying graph using the optimal solutions of these convex programs, we develop a new multi-stage primal-dual framework to analyze the fractional multi-stage algorithm that returns the corresponding regularized optimal matching in each stage (by solving the stage’s convex program). We further show a matching upper-bound by providing an unweighted instance of the problem in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
  • Theory of computation → Online algorithms
Keywords
  • Online Bipartite Matching
  • Primal-Dual Analysis
  • Multi-stage Allocation
  • Batching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1253-1264. SIAM, 2011. Google Scholar
  2. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail