Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== Title ==
New Approximation Results for Resource Replication Problems
== Speaker ==
Kanthi Kiran Sarpatwar
== Abstract ==
We consider several variants of a basic resource replication
problem in this paper, and propose new approximation results for them.
These problems are of fundamental interest in the areas of P2P net-
works, sensor networks and ad hoc networks, where optimal 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.
This is joint work with Samir Khuller and Barna Saha.
New Approximation Results for Resource Replication Problems
== Speaker ==
Kanthi Kiran Sarpatwar
== Abstract ==
We consider several variants of a basic resource replication
problem in this paper, and propose new approximation results for them.
These problems are of fundamental interest in the areas of P2P net-
works, sensor networks and ad hoc networks, where optimal 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.
This is joint work with Samir Khuller and Barna Saha.
