# Edge-weighted Matching in the Dark

arXiv: https://arxiv.org/abs/2507.19366 · HTML: https://mlsanity.com/paper/2507.19366/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Stochastic Matching via Local Sparsification](https://mlsanity.com/paper/2605.14195/) (2026)

## Abstract (arXiv)

We present a 0.659-competitive Quadratic Ranking algorithm for the Oblivious Bipartite Matching problem, a distribution-free version of Query-Commit Matching. This result breaks the 1-frac1e barrier, addressing an open question raised by Tang, Wu, and Zhang (JACM 2023). Moreover, the competitive ratio of this distribution-free algorithm improves the best existing 0.641 ratio for Query-Commit Matching achieved by the distribution-dependent algorithm of Chen, Huang, Li, and Tang (SODA 2025). Quadratic Ranking is a novel variant of the classic Ranking algorithm. We parameterize the algorithm with two functions, and let two key expressions in the definition and analysis of the algorithm be quadratic forms of the two functions. We show that the quadratic forms are the unique choices that satisfy a set of natural properties. Further, they allow us to optimize the choice of the two functions using powerful quadratic programming solvers.