On the list update problem with advice
From MaRDI portal
Publication:515679
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
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