Record Details

Metrical Service Systems with Multiple Servers

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Metrical Service Systems with Multiple Servers
 
Creator CHIPLUNKAR, A
VISHWANATHAN, S
 
Subject RANDOMIZED ALGORITHMS
VERTEX COVER
K-SERVERS
ONLINE
k-server
Metrical service system
Online
Approximation
 
Description The problem of metrical service systems with multiple servers (-MSSMS), proposed by Feuerstein (LATIN'98: Theoretical Informatics, Third Latin American Symposium, 1998), is to service requests, each of which is an -point subset of a metric space, using servers in an online manner, minimizing the distance traveled by the servers. We prove that Feuerstein's deterministic algorithm for -MSSMS actually achieves an improved competitive ratio of on uniform metrics. In the randomized online setting on uniform metrics, we give an algorithm which achieves a competitive ratio , beating the deterministic lower bound of . We prove that any randomized algorithm for -MSSMS on uniform metrics must be -competitive. For the offline -MSSMS, we give a factor pseudo-approximation algorithm using servers on any metric space, and prove a matching hardness result, that a pseudo-approximation using less than servers is unlikely, even on uniform metrics.
 
Publisher SPRINGER
 
Date 2016-01-14T11:00:10Z
2016-01-14T11:00:10Z
2015
 
Type Article
 
Identifier ALGORITHMICA, 71(1)219-231
0178-4617
1432-0541
http://dx.doi.org/10.1007/s00453-014-9903-7
http://dspace.library.iitb.ac.in/jspui/handle/100/17421
 
Language en