Adding Isolated Vertices Makes Some Online Algorithms Optimal

Joan Boyar, Christian Kudahl

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

Abstract

An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and Online Vertex Cover on graphs with “enough” isolated vertices, Freckle Graphs. For Online Dominating Set, the greedy algorithm is shown to be worst case online optimal on graphs with at least one isolated vertex. These algorithms are not online optimal in general. The online optimality results for these greedy algorithms imply optimality according to various worst case performance measures, such as the competitive ratio. It is also shown that, despite this worst case optimality, there are Freckle graphs where the greedy independent set algorithm is objectively less good than another algorithm.

It is shown that it is NP-hard to determine any of the following for a given graph: the online independence number, the online vertex cover number, and the online domination number.
Original languageEnglish
Title of host publicationCombinatorial Algorithms : 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers
EditorsZsuzsanna Lipták, William F. Smyth
PublisherSpringer
Publication date2016
Pages65-76
ISBN (Print)978-3-319-29515-2
ISBN (Electronic)978-3-319-29516-9
DOIs
Publication statusPublished - 2016
Event26th International Workshop on Combinatorial Algorithms - Verona, Italy
Duration: 5. Oct 20157. Oct 2015

Conference

Conference26th International Workshop on Combinatorial Algorithms
CountryItaly
CityVerona
Period05/10/201507/10/2015
SeriesLecture Notes in Computer Science
Volume9538
ISSN0302-9743

Fingerprint Dive into the research topics of 'Adding Isolated Vertices Makes Some Online Algorithms Optimal'. Together they form a unique fingerprint.

Cite this