Online Matching with General Arrivals
作者： Buddhima Gamlath , Michael Kapralov , Andreas Maggiori , Ola Svensson , David Wajc
关键词: Online algorithm 、 Combinatorics 、 Blossom algorithm 、 Competitive analysis 、 Randomized algorithm 、 Bipartite graph 、 Vertex (geometry) 、 Existential quantification 、 Computer science
摘要: The online matching problem was introduced by Karp, Vazirani and nearly three decades ago. In that seminal work, they studied this in bipartite graphs with vertices arriving only on one side, presented optimal deterministic randomized algorithms for setting. comparison, more general arrival models, such as edge arrivals vertex arrivals, have proven challenging positive results are known various relaxations of the problem. particular, even basic question whether randomization allows to beat trivially-optimal competitive ratio 1/2 either these models open. paper, we resolve both natural show following.1) For does not help --- no algorithm is better than competitive. 2)For helps there exists a (1/2+Ω(1)) -competitive algorithm.
arxiv.org
sci-hub.se 参考文章(27)
Ashish Chiplunkar, Sumedh Tirodkar, Sundar Vishwanathan, On Randomized Algorithms for Matching in the Online Preemptive Model european symposium on algorithms. pp. 325- 336 ,(2015) , 10.1007/978-3-662-48350-3_28
Jon Feldman, Nitish Korula, Vahab Mirrokni, S. Muthukrishnan, Martin Pál, Online Ad Assignment with Free Disposal Lecture Notes in Computer Science. pp. 374- 385 ,(2009) , 10.1007/978-3-642-10841-9_34
Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan, Dependent rounding and its applications to approximation algorithms Journal of the ACM. ,vol. 53, pp. 324- 360 ,(2006) , 10.1145/1147954.1147956
Gagan Goel, Aranyak Mehta, Online budgeted matching in random input models with applications to Adwords symposium on discrete algorithms. pp. 982- 991 ,(2008)
Benjamin Birnbaum, Claire Mathieu, On-line bipartite matching made simple Sigact News. ,vol. 39, pp. 80- 87 ,(2008) , 10.1145/1360443.1360462
Jack Edmonds, Paths, Trees, and Flowers Canadian Journal of Mathematics. ,vol. 17, pp. 361- 379 ,(1965) , 10.1007/978-0-8176-4842-8_26
A.A. Ageev, M.I. Sviridenko, Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee Journal of Combinatorial Optimization. ,vol. 8, pp. 307- 328 ,(2004) , 10.1023/B:JOCO.0000038913.96607.C2
R. M. Karp, U. V. Vazirani, V. V. Vazirani, An optimal algorithm for on-line bipartite matching symposium on the theory of computing. pp. 352- 358 ,(1990) , 10.1145/100216.100262
Aranyak Mehta, Online Matching and Ad Allocation ,(2013)
H. W. Kuhn, The Hungarian method for the assignment problem Naval Research Logistics Quarterly. ,vol. 2, pp. 83- 97 ,(1955) , 10.1002/NAV.3800020109