# Relaxing the Irrevocability Requirement for Online Graph Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2017.

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

- [Learning-Augmented Algorithms for Online Vertex Cover](https://mlsanity.com/paper/2606.22831/) (2026)

## Abstract (arXiv)

Online graph problems are considered in models where the irrevocability requirement is relaxed. Motivated by practical examples where, for example, there is a cost associated with building a facility and no extra cost associated with doing it later, we consider the Late Accept model, where a request can be accepted at a later point, but any acceptance is irrevocable. Similarly, we also consider a Late Reject model, where an accepted request can later be rejected, but any rejection is irrevocable (this is sometimes called preemption). Finally, we consider the Late Accept/Reject model, where late accepts and rejects are both allowed, but any late reject is irrevocable. For Independent Set, the Late Accept/Reject model is necessary to obtain a constant competitive ratio, but for Vertex Cover the Late Accept model is sufficient and for Minimum Spanning Forest the Late Reject model is sufficient. The Matching problem has a competitive ratio of 2, but in the Late Accept/Reject model, its competitive ratio is 3/2.