Online Matching with General Arrivals

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. 1) For edge arrivals, randomization does not help - no randomized algorithm is better than 1/2 competitive. 2)For general vertex arrivals, randomization helps - there exists a randomized (1/2+Ω(1)) -competitive online matching algorithm.

Authors

• Buddhima Gamlath
• Michael Kapralov
• Andreas Maggiori
• Ola Svensson
• David Wajc

Keywords

• Upper bound
• Bipartite graph
• Optimization
• Uncertainty
• Computer science
• Mathematical model
• Stochastic processes
• Online Matching
• Matching Algorithm
• Competitive Algorithm
• Competitive Ratio
• Hardness
• Feasible Solution
• Arrival Time
• Lossless
• Small Probability
• Formal Proof
• Dual Variables
• Online Algorithm
• Maximum Matching
• Fractional Solution
• Family Of Algorithms
• Step In This Line
• Vertex Cover
• Dual Solution
• Order Of Arrival
• Primary Path
• Dual Value
• Greedy Matching
• Symmetric Difference
• Induction Hypothesis
• Departure Time
• Linear Programming
• Positive Correlation
• Optimal Combination
• Family Of Graphs
• online algorithms
• edge arrivals
• general vertex arrivals