Relaxing the Irrevocability Requirement for Online Graph Algorithms

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

24 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.

Original languageEnglish
JournalAlgorithmica
Volume84
Issue number7
Pages (from-to)1916-1951
ISSN0178-4617
DOIs
Publication statusPublished - Jul 2022

Keywords

  • Competitive analysis
  • Graph algorithms
  • Online algorithms
  • Preemption
  • Recourse

Fingerprint

Dive into the research topics of 'Relaxing the Irrevocability Requirement for Online Graph Algorithms'. Together they form a unique fingerprint.

Cite this