License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.88
URN: urn:nbn:de:0030-drops-136272
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13627/
Feng, Yiding ;
Niazadeh, Rad
Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)
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.
BibTeX - Entry
@InProceedings{feng_et_al:LIPIcs.ITCS.2021.88,
author = {Yiding Feng and Rad Niazadeh},
title = {{Batching and Optimal Multi-Stage Bipartite Allocations}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {88:1--88:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13627},
URN = {urn:nbn:de:0030-drops-136272},
doi = {10.4230/LIPIcs.ITCS.2021.88},
annote = {Keywords: Online Bipartite Matching, Primal-Dual Analysis, Multi-stage Allocation, Batching}
}
|
Keywords: |
|
Online Bipartite Matching, Primal-Dual Analysis, Multi-stage Allocation, Batching |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
