- Relaxing the Irrevocability Requirement for Online Graph Algorithms.
- Joan Boyar, Lene M. Favrholdt, Michal Kotrbčík, and Kim S. Larsen.
In Fifteenth International Algorithms and Data Structures Symposium (WADS), Lecture Notes in Computer Science. Springer. Accepted for publication.
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.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
open access (297 KB)
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
Other publications by the author.