Correcting the Foundational Analysis of Karp--Vazirani--Vazirani (STOC 1990): A Rigorous Revision of the $1-1/e$ Upper Bound
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918215439876096 |
|---|---|
| author | Xu, Pan |
| author_facet | Xu, Pan |
| contents | We revisit the classical analysis of Karp, Vazirani, and Vazirani (KVV, STOC~1990), which established the well-known upper bound of $1 - 1/e$ as the limiting proportion of vertices that can be matched by any online procedure in a canonical bipartite structure. Although foundational, the original analysis contains several inaccuracies, including a fundamental technical gap in the treatment of the underlying discrete process. We give a transparent and fully rigorous reconstruction of the KVV argument by reformulating the evolution of available neighbors as a discrete-time death process and deriving a sharp upper bound via a simple factor-revealing linear program that captures the correct recurrence structure. This yields a precise bound $\lceil n(1 - 1/e) + 2 - 1/e \rceil$ on the expected number of matched vertices, refining the classical claim $n(1 - 1/e) + o(n)$. Our goal is not to optimize this upper bound, but to provide a mathematically sound and conceptually clean correction of the classical KVV analysis, while remaining faithful to its original combinatorial framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_09530 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Correcting the Foundational Analysis of Karp--Vazirani--Vazirani (STOC 1990): A Rigorous Revision of the $1-1/e$ Upper Bound Xu, Pan Data Structures and Algorithms 05C70, 68W20, 90B80, 60J20 We revisit the classical analysis of Karp, Vazirani, and Vazirani (KVV, STOC~1990), which established the well-known upper bound of $1 - 1/e$ as the limiting proportion of vertices that can be matched by any online procedure in a canonical bipartite structure. Although foundational, the original analysis contains several inaccuracies, including a fundamental technical gap in the treatment of the underlying discrete process. We give a transparent and fully rigorous reconstruction of the KVV argument by reformulating the evolution of available neighbors as a discrete-time death process and deriving a sharp upper bound via a simple factor-revealing linear program that captures the correct recurrence structure. This yields a precise bound $\lceil n(1 - 1/e) + 2 - 1/e \rceil$ on the expected number of matched vertices, refining the classical claim $n(1 - 1/e) + o(n)$. Our goal is not to optimize this upper bound, but to provide a mathematically sound and conceptually clean correction of the classical KVV analysis, while remaining faithful to its original combinatorial framework. |
| title | Correcting the Foundational Analysis of Karp--Vazirani--Vazirani (STOC 1990): A Rigorous Revision of the $1-1/e$ Upper Bound |
| topic | Data Structures and Algorithms 05C70, 68W20, 90B80, 60J20 |
| url | https://arxiv.org/abs/2503.09530 |