On the list update problem with advice

DOI10.1007/978-3-319-04921-2_17zbMATH Open1362.68295arXiv1311.7357OpenAlexW1803135286MaRDI QIDQ515679FDOQ515679

Authors: Shahin Kamali, Kim S. Larsen, Alejandro Lopez-Ortiz, Joan Boyar 

Publication date: 16 March 2017

Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)

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 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 $5/3$. 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.

Full work available at URL: https://arxiv.org/abs/1311.7357

Recommendations

• On the list update problem with advice
• Online algorithms with advice: the tape model
• On the Advice Complexity of Online Problems
• Online computation with advice
• Online Computation with Advice

zbMATH Keywords

online algorithmscompetitive analysisadvice complexitylist update

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Cites Work

• A locally adaptive data compression scheme
• Title not available (Why is that?)
• Advice Complexity of Online Coloring for Paths
• On Online Algorithms with Advice for the k-Server Problem
• Online Coloring of Bipartite Graphs with and without Advice
• On the Advice Complexity of the k-Server Problem
• Information complexity of online problems
• On the Advice Complexity of Online Problems
• Advice Complexity of the Online Coloring Problem
• The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
• Advice Complexity and Barely Random Algorithms
• Online computation with advice
• Two results on the list update problem
• Randomized competitive algorithms for the list update problem
• Average case analyses of list update algorithms, with applications to data compression
• Title not available (Why is that?)
• On the competitive theory and practice of online list accessing algorithms
• A combined BIT and TIMESTAMP algorithm for the list update problem
• Off-line algorithms for the list update problem
• On Advice Complexity of the k-server Problem under Sparse Metrics
• A Survey of Algorithms and Models for List Update
• Improved Randomized On-Line Algorithms for the List Update Problem
• How Much Information about the Future Is Needed?
• Title not available (Why is that?)
• Online Bin Packing with Advice of Small Size
• A competitive analysis of the list update problem with lookahead
• Optimal lower bounds for projective list update algorithms

Cited In (10)

• Online bin packing with advice of small size
• Online bin packing with advice
• Online computation with untrusted advice
• Optimal Online Edge Coloring of Planar Graphs with Advice
• The advice complexity of a class of hard online problems
• Wernick's list: a final update
• A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey
• Online Bin Packing with Advice of Small Size
• Parallel online algorithms for the bin packing problem
• On the advice complexity of the \(k\)-server problem under sparse metrics

This page was built for publication: On the list update problem with advice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515679)