On the advice complexity of the k-server problem

DOI10.1016/J.JCSS.2017.01.001zbMATH Open1370.68333OpenAlexW2578333369MaRDI QIDQ2396827FDOQ2396827

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

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

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)