On the List Update Problem with Advice

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

109 Downloads (Pure)

Resumé

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 are 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, Timestamp and
two members of the Mtf2 family of algorithms. We also show that Mtf2
algorithms are 2.5-competitive.
OriginalsprogEngelsk
TidsskriftInformation and Computation
Vol/bind253
Udgave nummerPart 3
Sider (fra-til)411-423
ISSN0890-5401
DOI
StatusUdgivet - 2017

Fingeraftryk

Competitive Ratio
Online Algorithms
Deterministic Algorithm
Update
Sufficient
Timestamp
Models of Computation
Optimal Solution
Lower bound
Upper bound
Partial
Unknown
Costs
Model

Emneord

  • list update
  • advice complexity
  • competitive analysis
  • online algorithms

Citer dette

Boyar, Joan ; Kamali, Shahin ; Larsen, Kim Skak ; López-Ortiz, Alejandro. / On the List Update Problem with Advice. I: Information and Computation. 2017 ; Bind 253, Nr. Part 3. s. 411-423.
@article{95f453c49600432c944025b2b442e66e,
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 informationabout the unknown parts of the input in the form of some bits of advicegenerated by a benevolent offline oracle. We show that advice of linear sizeis required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the otherhand, we show that surprisingly two bits of advice are sufficient to breakthe 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 algorithmwith smaller cost among three classical online algorithms, Timestamp andtwo members of the Mtf2 family of algorithms. We also show that Mtf2algorithms are 2.5-competitive.",
keywords = "list update, advice complexity, competitive analysis, online algorithms",
author = "Joan Boyar and Shahin Kamali and Larsen, {Kim Skak} and Alejandro L{\'o}pez-Ortiz",
year = "2017",
doi = "10.1016/j.ic.2016.06.007",
language = "English",
volume = "253",
pages = "411--423",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Heinemann",
number = "Part 3",

}

On the List Update Problem with Advice. / Boyar, Joan; Kamali, Shahin; Larsen, Kim Skak; López-Ortiz, Alejandro.

I: Information and Computation, Bind 253, Nr. Part 3, 2017, s. 411-423.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - On the List Update Problem with Advice

AU - Boyar, Joan

AU - Kamali, Shahin

AU - Larsen, Kim Skak

AU - López-Ortiz, Alejandro

PY - 2017

Y1 - 2017

N2 - We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial informationabout the unknown parts of the input in the form of some bits of advicegenerated by a benevolent offline oracle. We show that advice of linear sizeis required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the otherhand, we show that surprisingly two bits of advice are sufficient to breakthe 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 algorithmwith smaller cost among three classical online algorithms, Timestamp andtwo members of the Mtf2 family of algorithms. We also show that Mtf2algorithms are 2.5-competitive.

AB - We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial informationabout the unknown parts of the input in the form of some bits of advicegenerated by a benevolent offline oracle. We show that advice of linear sizeis required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the otherhand, we show that surprisingly two bits of advice are sufficient to breakthe 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 algorithmwith smaller cost among three classical online algorithms, Timestamp andtwo members of the Mtf2 family of algorithms. We also show that Mtf2algorithms are 2.5-competitive.

KW - list update

KW - advice complexity

KW - competitive analysis

KW - online algorithms

U2 - 10.1016/j.ic.2016.06.007

DO - 10.1016/j.ic.2016.06.007

M3 - Journal article

VL - 253

SP - 411

EP - 423

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - Part 3

ER -