On advice complexity of the k-server problem under sparse metrics
From MaRDI portal
Publication:2868631
DOI10.1007/978-3-319-03578-9_5zbMATH Open1346.68263OpenAlexW1847140466MaRDI QIDQ2868631FDOQ2868631
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
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
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Advice complexity of online coloring for paths
- On the advice complexity of the knapsack problem
- On online algorithms with advice for the \(k\)-server problem
- On the advice complexity of the set cover problem
- Online graph exploration with advice
- Online coloring of bipartite graphs with and without advice
- On the advice complexity of the \(k\)-server problem
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- Title not available (Why is that?)
- The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
- Online computation with advice
- Title not available (Why is that?)
- An Optimal On-Line Algorithm for K Servers on Trees
- The 3-server problem in the plane.
- On the competitive ratio of the work function algorithm for the \(k\)-server problem
- Compact and low delay routing labeling scheme for unit disk graphs
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- Collective Tree Spanners and Routing in AT-free Related Graphs
- Collective tree spanners of graphs
- Compact navigation and distance oracles for graphs with small treewidth
- Advice complexity and barely random algorithms
- A randomized algorithm for two servers in cross polytope spaces
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)
