Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2507.19366 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916863947046912 |
|---|---|
| author | Huang, Zhiyi Sun, Enze Wu, Xiaowei Zhao, Jiahao |
| author_facet | Huang, Zhiyi Sun, Enze Wu, Xiaowei Zhao, Jiahao |
| contents | 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-\frac{1}{e}$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19366 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Edge-weighted Matching in the Dark Huang, Zhiyi Sun, Enze Wu, Xiaowei Zhao, Jiahao Data Structures and Algorithms 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-\frac{1}{e}$ 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. |
| title | Edge-weighted Matching in the Dark |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.19366 |