TY - JOUR

T1 - New Approximation Results for Resource Replication Problems

AU - Khuller, Samir

AU - Saha, Barna

AU - Sarpatwar, Kanthi K.

N1 - Funding Information:
S. Khuller: Supported by NSF Awards CCF-0728839 and CCF-0937865, and a Google Research Award. B. Saha: Most of the work done when the author was at AT&T Shannon Research Laboratory. Partially supported by NSF Grant 1464310 K. K. Sarpatwar: Supported by NSF Grant CCF-0728839.

PY - 2016/3/1

Y1 - 2016/3/1

N2 - In the Basic Resource Replication problem, we are given a graph, embedded into a distance metric, and a set of data items. The goal is to assign one data item to each vertex so as to minimize the maximum distance any vertex has to travel to access all the data items. We consider several variants of this problem in this paper, and propose new approximation results for them. These problems are of fundamental interest in the areas of P2P networks, sensor networks and ad hoc networks, where placement of replicas is the main bottleneck on performance. We observe that the threshold graph technique, which has been applied to several (Formula presented.) -center type problems, yields simple and efficient approximation algorithms for resource replication problems. Our results range from positive (efficient, small constant factor, approximation algorithms) to extremely negative (impossibility of existence of any algorithm with non-trivial approximation guarantee, i.e., with positive approximation ratio) for different versions of the problem.

AB - In the Basic Resource Replication problem, we are given a graph, embedded into a distance metric, and a set of data items. The goal is to assign one data item to each vertex so as to minimize the maximum distance any vertex has to travel to access all the data items. We consider several variants of this problem in this paper, and propose new approximation results for them. These problems are of fundamental interest in the areas of P2P networks, sensor networks and ad hoc networks, where placement of replicas is the main bottleneck on performance. We observe that the threshold graph technique, which has been applied to several (Formula presented.) -center type problems, yields simple and efficient approximation algorithms for resource replication problems. Our results range from positive (efficient, small constant factor, approximation algorithms) to extremely negative (impossibility of existence of any algorithm with non-trivial approximation guarantee, i.e., with positive approximation ratio) for different versions of the problem.

KW - Approximation algorithms

KW - Hardness of approximation

KW - Resource replication problems

UR - http://www.scopus.com/inward/record.url?scp=84959192264&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959192264&partnerID=8YFLogxK

U2 - 10.1007/s00453-015-9978-9

DO - 10.1007/s00453-015-9978-9

M3 - Article

AN - SCOPUS:84959192264

VL - 74

SP - 969

EP - 991

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 3

ER -