On the List Update Problem with Advice

Joan Boyar; Shahin Kamali; Kim Skak Larsen; Alejandro López-Ortiz

doi:10.1007/978-3-319-04921-2_17

On the List Update Problem with Advice

Joan Boyar, Shahin Kamali, Kim Skak Larsen, Alejandro López-Ortiz

Institut for Matematik og Datalogi

University of Waterloo

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice is sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 1.6¯ . In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms.

Originalsprog	Engelsk
Titel	Language and Automata Theory and Applications : 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings
Redaktører	Adrian-Horia Dediu et al.
Forlag	Springer
Publikationsdato	2014
Sider	210-221
ISBN (Trykt)	978-3-319-04920-5
ISBN (Elektronisk)	978-3-319-04921-2
DOI	https://doi.org/10.1007/978-3-319-04921-2_17
Status	Udgivet - 2014
Begivenhed	8th International Conference on Language and Automata Theory and Applications - Madrid, Spanien Varighed: 10. mar. 2014 → 14. mar. 2014 Konferencens nummer: 8

Konference

Konference	8th International Conference on Language and Automata Theory and Applications
Nummer	8
Land/Område	Spanien
By	Madrid
Periode	10/03/2014 → 14/03/2014

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

Emneord

online algorithms
list update problem
advice complexity

Dokumenter og links

10.1007/978-3-319-04921-2_17

Citationsformater

Boyar, J., Kamali, S., Larsen, K. S., & López-Ortiz, A. (2014). On the List Update Problem with Advice. I A-H. Dediu et al. (red.), Language and Automata Theory and Applications: 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings (s. 210-221). Springer. Lecture Notes in Computer Science Bind 8370 https://doi.org/10.1007/978-3-319-04921-2_17

@inproceedings{5b11f494afbc4843abb45828aac75f0b,

title = "On the List Update Problem with Advice",

abstract = "We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice is sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 1.6¯ . In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms.",

keywords = "online algorithms, list update problem, advice complexity",

author = "Joan Boyar and Shahin Kamali and Larsen, {Kim Skak} and Alejandro L{\'o}pez-Ortiz",

year = "2014",

doi = "10.1007/978-3-319-04921-2_17",

language = "English",

isbn = "978-3-319-04920-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "210--221",

editor = "{Dediu et al.}, Adrian-Horia",

booktitle = "Language and Automata Theory and Applications",

address = "Germany",

note = "8th International Conference on Language and Automata Theory and Applications ; Conference date: 10-03-2014 Through 14-03-2014",

}

Boyar, J, Kamali, S, Larsen, KS & López-Ortiz, A 2014, On the List Update Problem with Advice. i A-H Dediu et al. (red.), Language and Automata Theory and Applications: 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings. Springer, Lecture Notes in Computer Science, bind 8370, s. 210-221, 8th International Conference on Language and Automata Theory and Applications, Madrid, Spanien, 10/03/2014. https://doi.org/10.1007/978-3-319-04921-2_17

On the List Update Problem with Advice. / Boyar, Joan; Kamali, Shahin; Larsen, Kim Skak et al.

Language and Automata Theory and Applications: 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings. red. / Adrian-Horia Dediu et al. Springer, 2014. s. 210-221 (Lecture Notes in Computer Science, Bind 8370).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - On the List Update Problem with Advice

AU - Boyar, Joan

AU - Kamali, Shahin

AU - Larsen, Kim Skak

AU - López-Ortiz, Alejandro

N1 - Conference code: 8

PY - 2014

Y1 - 2014

N2 - We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice is sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 1.6¯ . In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms.

AB - We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice is sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 1.6¯ . In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms.

KW - online algorithms

KW - list update problem

KW - advice complexity

U2 - 10.1007/978-3-319-04921-2_17

DO - 10.1007/978-3-319-04921-2_17

M3 - Article in proceedings

SN - 978-3-319-04920-5

T3 - Lecture Notes in Computer Science

SP - 210

EP - 221

BT - Language and Automata Theory and Applications

A2 - Dediu et al., Adrian-Horia

PB - Springer

T2 - 8th International Conference on Language and Automata Theory and Applications

Y2 - 10 March 2014 through 14 March 2014

ER -

On the List Update Problem with Advice

Abstract

Konference

Emneord

Dokumenter og links

Fingeraftryk

Citationsformater