On advice complexity of the k-server problem under sparse metrics

DOI10.1007/978-3-319-03578-9_5MaRDI QIDQ2868631zbMATH OpenOpenAlexFDO

Authors Sushmita Gupta, Shahin Kamali, Alejandro Lopez-Ortiz

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-03578-9_5

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the advice complexity of the \(k\)-server problem under sparse metrics
• On online algorithms with advice for the \(k\)-server problem
• On online algorithms with advice for the k-server problem
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the \(k\)-server problem

Cites work

• scientific article; zbMATH DE number 432777 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• A randomized algorithm for two servers in cross polytope spaces
• Advice complexity and barely random algorithms
• Advice complexity of online coloring for paths
• An Optimal On-Line Algorithm for K Servers on Trees
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Collective tree spanners of graphs
• Compact and low delay routing labeling scheme for unit disk graphs
• Compact navigation and distance oracles for graphs with small treewidth
• Information complexity of online problems
• On online algorithms with advice for the \(k\)-server problem
• On the Advice Complexity of Online Problems
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the knapsack problem
• On the advice complexity of the set cover problem
• On the competitive ratio of the work function algorithm for the k-server problem
• Online coloring of bipartite graphs with and without advice
• Online computation with advice
• Online graph exploration with advice
• The 3-server problem in the plane.
• The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)

Cited in

(16)

• On the advice complexity of online bipartite matching and online stable marriage
• Online algorithms with advice for bin packing and scheduling problems
• On the advice complexity of the online dominating set problem
• The advice complexity of a class of hard online problems
• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
• On online algorithms with advice for the k-server problem
• Disjoint path allocation with sublinear advice
• On the advice complexity of the \(k\)-server problem
• Towards using the history in online computation with advice
• A technique to obtain hardness results for randomized online algorithms -- a survey
• On online algorithms with advice for the \(k\)-server problem
• On energy-efficient computations with advice
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Advice complexity of the online search problem
• Treasure hunt with advice
• Online algorithms with advice: the tape model

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

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