On the advice complexity of the \(k\)-server problem
From MaRDI portal
Publication:2396827
DOI10.1016/j.jcss.2017.01.001zbMath1370.68333MaRDI QIDQ2396827
Rastislav Královič, Dennis Komm, Hans-Joachim Böckenhauer, Richard Královič
Publication date: 26 May 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2017.01.001
Related Items
On conceptually simple algorithms for variants of online bipartite matching, Online Minimum Spanning Tree with Advice, Online bin covering with advice, Fully Online Matching with Advice on General Bipartite Graphs and Paths, Online algorithms with advice: the tape model, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, Call admission problems on grids with advice, Online two-way trading: randomization and advice, Online Graph Coloring Against a Randomized Adversary
Cites Work
- Unnamed Item
- Unnamed Item
- The \(k\)-server problem
- Online computation with advice
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- On online algorithms with advice for the \(k\)-server problem
- The online knapsack problem: advice and randomization
- On Advice Complexity of the k-server Problem under Sparse Metrics
- On the Advice Complexity of the k-Server Problem
- On the Power of Randomness versus Advice in Online Computation
- Disjoint Path Allocation with Sublinear Advice
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- On the k -server conjecture
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- Advice Complexity and Barely Random Algorithms
- Measuring the problem-relevant information in input
- A Polylogarithmic-Competitive Algorithm for the k-Server Problem
- On the Length of Programs for Computing Finite Binary Sequences
