On the advice complexity of the k-server problem

DOI10.1016/J.JCSS.2017.01.001MaRDI QIDQ2396827zbMATH OpenOpenAlexFDO

Authors Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, 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

zbMATH Keywords

online algorithmscompetitive analysisadvice complexity\(k\)-server problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20)

Recommendations

• On the advice complexity of the \(k\)-server problem
• On online algorithms with advice for the \(k\)-server problem
• On online algorithms with advice for the \(k\)-server problem
• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• Advice complexity and barely random algorithms
• Design and analysis of randomized algorithms. Introduction to design paradigms.
• Disjoint path allocation with sublinear advice
• Information complexity of online problems
• Measuring the problem-relevant information in input
• On advice complexity of the \(k\)-server problem under sparse metrics
• On online algorithms with advice for the \(k\)-server problem
• On the k -server conjecture
• On the Advice Complexity of Online Problems
• On the Length of Programs for Computing Finite Binary Sequences
• On the advice complexity of the \(k\)-server problem
• On the power of randomness versus advice in online computation
• Online computation with advice
• Randomization can be as helpful as a glimpse of the future in online computation
• The \(k\)-server problem
• The online knapsack problem: advice and randomization
• The string guessing problem as a method to prove lower bounds on the advice complexity

Cited in

(18)

• On the advice complexity of the \(k\)-server problem
• Online computation with advice
• On online algorithms with advice for the \(k\)-server problem
• Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems
• Call admission problems on grids with advice
• On online algorithms with advice for the \(k\)-server problem
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• A note on the server problem and a benevolent adversary
• On advice complexity of the \(k\)-server problem under sparse metrics
• Online graph coloring against a randomized adversary
• Online Computation with Advice
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Online algorithms with advice: the tape model
• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
• Online two-way trading: randomization and advice
• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
• Online bin covering with advice
• Online Minimum Spanning Tree with Advice

This page was built for publication: On the advice complexity of the \(k\)-server problem

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