文章基本信息

标题：Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)
本地全文：下载
作者：Yiding Feng ; Rad Niazadeh
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：185
页码：88:1-88:1
DOI：10.4230/LIPIcs.ITCS.2021.88
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Online Bipartite Matching; Primal-Dual Analysis; Multi-stage Allocation; Batching