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

Institut for Matematik og Datalogi

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Combinatorial Algorithms : 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers
Redaktører	Zsuzsanna Lipták, William F. Smyth
Forlag	Springer
Publikationsdato	2016
Sider	65-76
ISBN (Trykt)	978-3-319-29515-2
ISBN (Elektronisk)	978-3-319-29516-9
DOI	https://doi.org/10.1007/978-3-319-29516-9_6
Status	Udgivet - 2016
Begivenhed	26th International Workshop on Combinatorial Algorithms - Verona, Italien Varighed: 5. okt. 2015 → 7. okt. 2015

Konference

Konference	26th International Workshop on Combinatorial Algorithms
Land/Område	Italien
By	Verona
Periode	05/10/2015 → 07/10/2015

Navn	Lecture Notes in Computer Science
Vol/bind	9538
ISSN	0302-9743

Emneord

online algorithms
greedy algorithms
isolated vertices

Dokumenter og links

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

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@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. i Z Lipták & WF Smyth (red), Combinatorial Algorithms: 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers. Springer, Lecture Notes in Computer Science, bind 9538, s. 65-76, 26th International Workshop on Combinatorial Algorithms, Verona, Italien, 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. red. / Zsuzsanna Lipták; William F. Smyth. Springer, 2016. s. 65-76 (Lecture Notes in Computer Science, Bind 9538).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater