Relaxing the Irrevocability Requirement for Online Graph Algorithms

Joan Boyar, Lene M. Favrholdt, Michal Kotrbčík, Kim S. Larsen*

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

31 Downloads (Pure)

Abstract

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.

OriginalsprogEngelsk
TidsskriftAlgorithmica
Vol/bind84
Udgave nummer7
Sider (fra-til)1916-1951
ISSN0178-4617
DOI
StatusUdgivet - jul. 2022

Bibliografisk note

Funding Information:
This work was supported in part by the Danish Council for Independent Research, Natural Sciences, Grant DFF-1323-00247, the Independent Research Fund Denmark, Natural Sciences, Grants DFF-7014-00041 and DFF-0135-00018B, and the Villum Foundation, grant VKR023219. A preliminary version of the paper appeared in the 15th International Algorithms and Data Structures Symposium (WADS), volume 10389 of Lecture Notes in Computer Science, pages 217–228. Springer, 2017.

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Relaxing the Irrevocability Requirement for Online Graph Algorithms'. Sammen danner de et unikt fingeraftryk.

Citationsformater