Tight Bound for Online Vertex Cover under Edge Arrivals
What is the optimal competitive ratio for online vertex cover when edges arrive one at a time? The paper proves a tight factor-2 lower bound via a reduction in the blueprint framework of Assadi, Jiang and Xiang, closing the gap left by prior work.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Online algorithms
- Posed by
- —
- Year posed
- —
- Years open
- —
- Solved
- 2026-08-05
- Model
- GPT-5.6 Sol
- Vendor
- OpenAI
- Collaborators
- Zhihao Gavin Tang
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The authors had partial progress and suggested the Assadi-Jiang-Xiang blueprint might apply; "prompted by this suggestion, OpenAI's GPT-5.6 Sol formulated the reduction yielding the tight factor-2 lower bound proved in this paper and assisted with drafting the manuscript." The authors independently verified the reduction, proof and citations.