Improved algorithm boosts online matching with weighted edges beyond 55 percent
Online Edge-Weighted Matching Beyond 0.55
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
Online matching problems ask how to pair things arriving one by one in the best possible way. This paper improves a known algorithm that tries to find the heaviest matching between two groups with weights on the connections. The new algorithm achieves better performance, about 55.6% of the optimal in tough cases, beating the previous 53.7%. It uses a sophisticated way to track choices using probabilities depending on past decisions, analyzed carefully with math tools and computer checks. This work shows the limits of this approach by matching a certain known hard example exactly.
What this means in practice
- •For online marketplace designers: Improve algorithms for dynamically matching buyers and sellers when connection values vary and items appear over time.
- •For real-time ad allocation teams: Enhance decision systems for assigning ads to user impressions to maximize weighted value despite uncertain and sequential arrivals.
Authors
Alireza Farhadi, Mohammad Hajiaghayi
Abstract
We give a $0.556195$-competitive randomized algorithm for edge-weighted online bipartite matching with free disposal, improving the $0.5368$ guarantee of Blanc and Charikar. The result holds for arbitrary nonnegative edge weights and any input sequence fixed independently of the algorithm's randomness. Our algorithm builds on online correlated selection, introduced by Fahrbach, Huang, Tao, and Zadimoghaddam, and its multiway extension due to Blanc and Charikar. Our main contribution is a state-dependent primal--dual analysis of correlated selection. At each weight threshold, we track the state of the selection process jointly with an auxiliary failure event. The analysis accounts for arrivals below the threshold, which change the state without improving the matching value at that threshold. A potential function bounds the dual increase in both cases. We instantiate the analysis with an explicit win map that assigns a common score to an initial range of states. Its selection inequalities are verified by a finite computer-assisted proof covering every required candidate multiplicity and every real threshold; the verifiers are available in an accompanying repository. Triangular unit-weight inputs asymptotically attain the guarantee of the underlying ideal algorithm, proving that its analysis is tight.