New Approximation Results for Resource Replication Problems

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...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2016-03, Vol.74 (3), p.969-991
Main Authors: Khuller, Samir, Saha, Barna, Sarpatwar, Kanthi K.
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Mathematics of Computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 k -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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-015-9978-9