Metraipolis › archive › dc_2b62cbe8a950

A New Lower Bound for Online Vertex Cover under Vertex Arrivals — arXiv:2608.09210

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.09210
License (as archived)
CC0-1.0
Archived
2026-10-19T08:55:51.625Z
SHA-256 of the archived text
91ad5dec50756fd3446d78bde94d49107c5cba42e12fe12e6a35b7cc384d7a11
Stable URL of this page
https://metraipolis.com/documento/dc_2b62cbe8a950

How to cite

A New Lower Bound for Online Vertex Cover under Vertex Arrivals — arXiv:2608.09210 — arXiv (en), https://arxiv.org/abs/2608.09210 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2b62cbe8a950 (Metraipolis archive dc_2b62cbe8a950, sha256 91ad5dec50756fd3446d78bde94d49107c5cba42e12fe12e6a35b7cc384d7a11)
BibTeX
@misc{dc2b62cbe8a950,
  title = {A New Lower Bound for Online Vertex Cover under Vertex Arrivals — arXiv:2608.09210},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.09210},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2b62cbe8a950; sha256 91ad5dec50756fd3446d78bde94d49107c5cba42e12fe12e6a35b7cc384d7a11},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09210. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. Our proof extends the complete-bipartite alternating construction of Wang and Wong to an arbitrary number of alternations. The resulting adversary is described by a monotone integral recurrence. If the recurrence never violates the competitive budget, its iterates converge to an integrable fixed point; classifying all such fixed points forces the excess ratio to be at least $\sqrt{e}/2$. A truncated discrete recurrence and a Riemann-sum argument convert every strict continuous violation into a finite, algorithm-dependent but realization-oblivious input. We also exhibit a critical fixed point showing that $1+\sqrt{e}/2$ is the exact limit of this homogeneous complete-bipartite recurrence, rather than a numerical artifact.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-11 in cs.GT).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.09210 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T08:52:22.710Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).