Online Stochastic Matching: New Algorithms and Bounds
- PDF / 7,374,259 Bytes
- 47 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 255 Views
Online Stochastic Matching: New Algorithms and Bounds Brian Brubach1 · Karthik Abinav Sankararaman1 · Aravind Srinivasan1 · Pan Xu2 Received: 19 June 2018 / Accepted: 10 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Online matching has received significant attention in recent years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 − 1∕𝖾) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the “known I.I.D. model” where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam (WINE, 2011) to 0.705; and (b) the vertexweighted case, where we improve the 0.7250 ratio of Jaillet and Lu (Math Oper Res 39(3):624–646, 2013) to 0.7299. We also consider an extension of stochastic rewards, a variant where each edge has an independent probability of being present. For the setting of stochastic rewards with non-integral arrival rates, we present a simple optimal non-adaptive algorithm with a ratio of 1 − 1∕𝖾 . For the special case where each edge is unweighted and has a uniform constant probability of being present, we improve upon 1 − 1∕𝖾 by proposing a strengthened LP benchmark. One of the key ingredients of our improvement is the following (offline) approach to bipartite-matching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution 𝐟 ; however, these give us less control over the structure of 𝐟 . We next remove all these additional constraints and randomly move from 𝐟 to a feasible point on the matching polytope with all coordinates being from the set {0, 1∕k, 2∕k, … , 1} for a chosen integer k. The structure of this solution is inspired by Jaillet and Lu (2013) and is a tractable structure for algorithm design and analysis. The appropriate random move preserves many of the removed constraints (approximately with high probability and exactly in expectation). This underlies some of our improvements and could be of independent interest. A preliminary version of this appeared in the European Symposium on Algorithms (ESA), 2016. Supported in part by NSF awards CCF-1422569 and CCF-1749864, and by research awards from Adobe, Amazon, and Google. Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
Keywords Online algorithms · Randomized algorithms · Bipartite matching · Internet advertising
1 Introduction Applications to Internet advertising have driven the study of online matching problems in recent years [18]. In these problems, we consider a bipartite graph G = (U, V, E)
Data Loading...
