- Relaxing the Irrevocability Requirement for Online Graph Algorithms.
- Joan Boyar, Lene M. Favrholdt, Michal Kotrbčík, and Kim S. Larsen.
Algorithmica. Accepted for publication.
Online graph problems are considered in models where the
irrevocability requirement is relaxed. We consider the Late Accept
model, where a request can be accepted at a later point, but any
acceptance is irrevocable. Similarly, we 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. We consider
four classical graph problems: For Maximum Independent Set, the Late
Accept/Reject model is necessary to obtain a constant competitive
ratio, for Minimum Vertex Cover the Late Accept model is sufficient,
and for Minimum Spanning Forest the Late Reject model is
sufficient. The Maximum Matching problem admits constant competitive
ratios in all cases. We also consider Maximum Acyclic Subgraph and
Maximum Planar Subgraph, which exhibit patterns similar to Maximum
Independent Set.
-
other publications
-
Other publications by the author.