arXiv preprint ·
Online Edge-Weighted Matching Beyond 0.55
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Sublinear Metric Distortion for Matching
Learning and Steering in Incomplete-Information Games
AI-Assisted Classification under Correlation Neglect and Trust
Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism
Offline Learning of Reserve Prices from Censored Bids
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.