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

DOI10.1007/S00224-015-9649-XzbMATH Open1401.68368arXiv1305.2108OpenAlexW2467644617MaRDI QIDQ503460FDOQ503460

Authors: Sushmita Gupta, Shahin Kamali, Alejandro Lopez-Ortiz 

Publication date: 12 January 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we show that an advice of size {Omega}(n) is required to obtain a 1-competitive algorithm for sequences of size n, even for the 2-server problem on a path metric of size N >= 5. Through another lower bound argument, we show that at least (n/2)(log {alpha} - 1.22) bits of advice is required to obtain an optimal solution for metric spaces of treewidth {alpha}, where 4 <= {alpha} < 2k. On the other side, we introduce {Theta}(1)-competitive algorithms for a wide range of sparse graphs, which require advice of (almost) linear size. Namely, we show that for graphs of size N and treewidth {alpha}, there is an online algorithm which receives $O(n(logalpha+loglogN))$ bits of advice and optimally serves a sequence of length n. With a different argument, we show that if a graph admits a system of {mu} collective tree (q,r)-spanners, then there is a (q+r)-competitive algorithm which receives O(n (log {mu} + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, provided with O(n log log N) bits of advice.

Full work available at URL: https://arxiv.org/abs/1305.2108

Recommendations

• On 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

zbMATH Keywords

competitive analysisadvice complexity\(k\)-server problem

Mathematics Subject Classification ID

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

Cites Work

• The online knapsack problem: advice and randomization
• Advice complexity of online coloring for paths
• On online algorithms with advice for the \(k\)-server problem
• On the advice complexity of the set cover problem
• Online graph exploration with 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?)
• Online coloring of bipartite graphs with and without advice
• Advice complexity of the online coloring problem
• Online computation with advice
• Random walks on weighted graphs and applications to on-line algorithms
• Competitive randomized algorithms for nonuniform problems
• The 2-evader problem
• Title not available (Why is that?)
• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive algorithms for server problems
• On the k -server conjecture
• S-functions for graphs
• The 3-server problem in the plane.
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• On embedding trees into uniformly convex Banach spaces
• New Ressults on Server Problems
• Graph minors. III. Planar tree-width
• On advice complexity of the \(k\)-server problem under sparse metrics
• 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
• How Much Information about the Future Is Needed?
• Online bin packing with advice
• Title not available (Why is that?)
• 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
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• The string guessing problem as a method to prove lower bounds on the advice complexity

Cited In (7)

• Online bin packing with advice of small size
• 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
• On online algorithms with advice for the \(k\)-server problem

This page was built for publication: On the 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 Q503460)