Metrical service systems with multiple servers

DOI10.1007/S00453-014-9903-7MaRDI QIDQ2258084zbMATH OpenOpenAlexFDO

Authors Ashish Chiplunkar, Sundar Vishwanathan

Publication date 2 March 2015

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-serverapproximationmetrical service systemonline

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Abstract: We study the problem of metrical service systems with multiple servers (MSSMS), which generalizes two well-known problems -- the $k$-server problem, and metrical service systems. The MSSMS problem is to service requests, each of which is an $l$-point subset of a metric space, using $k$ servers, with the objective of minimizing the total distance traveled by the servers. Feuerstein initiated a study of this problem by proving upper and lower bounds on the deterministic competitive ratio for uniform metric spaces. We improve Feuerstein's analysis of the upper bound and prove that his algorithm achieves a competitive ratio of $k(k+lchoosel-1)$. In the randomized online setting, for uniform metric spaces, we give an algorithm which achieves a competitive ratio $mathcalO(k^{3}logl)$, beating the deterministic lower bound of $k+lchoosel-1$. We prove that any randomized algorithm for MSSMS on uniform metric spaces must be $Omega(logkl)$-competitive. We then prove an improved lower bound of $k+2l-1choosek-k+l-1choosek$ on the competitive ratio of any deterministic algorithm for $(k,l)$-MSSMS, on general metric spaces. In the offline setting, we give a pseudo-approximation algorithm for $(k,l)$-MSSMS on general metric spaces, which achieves an approximation ratio of $l$ using $kl$ servers. We also prove a matching hardness result, that a pseudo-approximation with less than $kl$ servers is unlikely, even for uniform metric spaces. For general metric spaces, we highlight the limitations of a few popular techniques, that have been used in algorithm design for the $k$-server problem and metrical service systems.

Recommendations

• Metrical service systems with multiple servers
• Competitive algorithms for generalized k-server in uniform metrics
• scientific article; zbMATH DE number 1559591
• Online k-Server Routing Problems
• scientific article; zbMATH DE number 6469207

Cites work

• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• A primal-dual randomized algorithm for weighted paging
• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive k-server algorithms
• Competitive Algorithms for Layered Graph Traversal
• Competitive algorithms for the weighted server problem
• Competitive randomized algorithms for nonuniform problems
• scientific article; zbMATH DE number 15120 (Why is no real title available?)
• scientific article; zbMATH DE number 65695 (Why is no real title available?)
• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• Metrical service systems with multiple servers
• New Ressults on Server Problems
• On randomization in on-line computation.
• On the k -server conjecture
• On the power of unique 2-prover 1-round games
• On Traversing Layered Graphs On-Line
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• Shortest paths without a map
• The \(k\)-server problem
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• The harmonic k -server algorithm is competitive
• The importance of being biased
• The weighted 2-server problem
• Traversing Layered Graphs Using the Work Function Algorithm
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(3)

• Metrical service systems with multiple servers
• Parametrized Metrical Task Systems
• Online paging with heterogeneous cache slots

This page was built for publication: Metrical service systems with multiple servers

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