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

Department of Mathematics and Computer Science

University of Waterloo

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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.

Original language	English
Title of host publication	Language and Automata Theory and Applications : 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings
Editors	Adrian-Horia Dediu et al.
Publisher	Springer
Publication date	2014
Pages	210-221
ISBN (Print)	978-3-319-04920-5
ISBN (Electronic)	978-3-319-04921-2
DOIs	https://doi.org/10.1007/978-3-319-04921-2_17
Publication status	Published - 2014
Event	8th International Conference on Language and Automata Theory and Applications - Madrid, Spain Duration: 10. Mar 2014 → 14. Mar 2014 Conference number: 8

Conference

Conference	8th International Conference on Language and Automata Theory and Applications
Number	8
Country/Territory	Spain
City	Madrid
Period	10/03/2014 → 14/03/2014

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

Documents & Links

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

SDU Link

Check access to the material in SDU Library's search engine

Cite this

@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. in A-H Dediu et al. (ed.), Language and Automata Theory and Applications: 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings. Springer, Lecture Notes in Computer Science, vol. 8370, pp. 210-221, 8th International Conference on Language and Automata Theory and Applications, Madrid, Spain, 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. ed. / Adrian-Horia Dediu et al. Springer, 2014. p. 210-221 (Lecture Notes in Computer Science, Vol. 8370).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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

Conference

Documents & Links

SDU Link

Fingerprint

Cite this