On the list update problem with advice

DOI10.1016/j.ic.2016.06.007zbMath1362.68295arXiv1311.7357OpenAlexW1803135286MaRDI QIDQ515679

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

Publication date: 16 March 2017

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

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

zbMATH Keywords

competitive analysisonline algorithmsadvice complexitylist update

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Related Items (8)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online computation with advice
• A combined BIT and TIMESTAMP algorithm for the list update problem
• A competitive analysis of the list update problem with lookahead
• Two results on the list update problem
• Randomized competitive algorithms for the list update problem
• Off-line algorithms for the list update problem
• Average case analyses of list update algorithms, with applications to data compression
• A Survey of Algorithms and Models for List Update
• On Advice Complexity of the k-server Problem under Sparse Metrics
• 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
• Optimal lower bounds for projective list update algorithms
• On the Advice Complexity of the k-Server Problem
• Online Bin Packing with Advice of Small Size
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• A locally adaptive data compression scheme
• Improved Randomized On-Line Algorithms for the List Update Problem
• 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
• How Much Information about the Future Is Needed?
• On the competitive theory and practice of online list accessing algorithms

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