Adding Isolated Vertices Makes Some Online Algorithms Optimal

Joan Boyar; Christian Kudahl

doi:10.1007/978-3-319-29516-9_6

Adding Isolated Vertices Makes Some Online Algorithms Optimal

Joan Boyar, Christian Kudahl

Department of Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Combinatorial Algorithms : 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers
Editors	Zsuzsanna Lipták, William F. Smyth
Publisher	Springer
Publication date	2016
Pages	65-76
ISBN (Print)	978-3-319-29515-2
ISBN (Electronic)	978-3-319-29516-9
DOIs	https://doi.org/10.1007/978-3-319-29516-9_6
Publication status	Published - 2016
Event	26th International Workshop on Combinatorial Algorithms - Verona, Italy Duration: 5. Oct 2015 → 7. Oct 2015

Conference

Conference	26th International Workshop on Combinatorial Algorithms
Country/Territory	Italy
City	Verona
Period	05/10/2015 → 07/10/2015

Series	Lecture Notes in Computer Science
Volume	9538
ISSN	0302-9743

Documents & Links

10.1007/978-3-319-29516-9_6

Cite this

@inproceedings{f416778eefa14ec89aeb83512fced14a,

title = "Adding Isolated Vertices Makes Some Online Algorithms Optimal",

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.",

keywords = "online algorithms, greedy algorithms, isolated vertices",

author = "Joan Boyar and Christian Kudahl",

year = "2016",

doi = "10.1007/978-3-319-29516-9_6",

language = "English",

isbn = "978-3-319-29515-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "65--76",

editor = "Zsuzsanna Lipt{\'a}k and Smyth, {William F.}",

booktitle = "Combinatorial Algorithms",

address = "Germany",

note = "26th International Workshop on Combinatorial Algorithms, IWOCA ; Conference date: 05-10-2015 Through 07-10-2015",

}

Boyar, J & Kudahl, C 2016, Adding Isolated Vertices Makes Some Online Algorithms Optimal. in Z Lipták & WF Smyth (eds), Combinatorial Algorithms: 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers. Springer, Lecture Notes in Computer Science, vol. 9538, pp. 65-76, 26th International Workshop on Combinatorial Algorithms, Verona, Italy, 05/10/2015. https://doi.org/10.1007/978-3-319-29516-9_6

Adding Isolated Vertices Makes Some Online Algorithms Optimal. / Boyar, Joan; Kudahl, Christian.
Combinatorial Algorithms: 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers. ed. / Zsuzsanna Lipták; William F. Smyth. Springer, 2016. p. 65-76 (Lecture Notes in Computer Science, Vol. 9538).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Adding Isolated Vertices Makes Some Online Algorithms Optimal

AU - Boyar, Joan

AU - Kudahl, Christian

PY - 2016

Y1 - 2016

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

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

KW - online algorithms

KW - greedy algorithms

KW - isolated vertices

U2 - 10.1007/978-3-319-29516-9_6

DO - 10.1007/978-3-319-29516-9_6

M3 - Article in proceedings

SN - 978-3-319-29515-2

T3 - Lecture Notes in Computer Science

SP - 65

EP - 76

BT - Combinatorial Algorithms

A2 - Lipták, Zsuzsanna

A2 - Smyth, William F.

PB - Springer

T2 - 26th International Workshop on Combinatorial Algorithms

Y2 - 5 October 2015 through 7 October 2015

ER -

Adding Isolated Vertices Makes Some Online Algorithms Optimal

Abstract

Conference

Documents & Links

Fingerprint

Cite this