Relaxing the Irrevocability Requirement for Online Graph Algorithms

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

143 Downloads (Pure)

Abstract

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
PublisherSpringer
Publication date2017
Pages217-228
ISBN (Print)978-3-319-62126-5
ISBN (Electronic)978-3-319-62127-2
DOIs
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

Conference

Conference15th International Algorithms and Data Structures Symposium 2017
Number15
LocationMemorial University of Newfoundland
Country/TerritoryCanada
CitySt. John's, Newfoundland and Labrador
Period30/07/201702/08/2017
SeriesLecture Notes in Computer Science
Volume10389
ISSN0302-9743

Fingerprint

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

Cite this