Relaxing the Irrevocability Requirement for Online Graph Algorithms

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

143 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures : Proceedings of the 15th International Symposium on Algorithms and Data Structures
EditorsFaith Ellen, Antonina Kolokolova, Jörg-Rüdiger Sack
Publication date2017
ISBN (Print)978-3-319-62126-5
ISBN (Electronic)978-3-319-62127-2
Publication statusPublished - 2017
Event15th International Algorithms and Data Structures Symposium 2017 - Memorial University of Newfoundland, St. John's, Newfoundland and Labrador, Canada
Duration: 30. Jul 20172. Aug 2017
Conference number: 15


Conference15th International Algorithms and Data Structures Symposium 2017
LocationMemorial University of Newfoundland
CitySt. John's, Newfoundland and Labrador
SeriesLecture Notes in Computer Science


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

Cite this