Changes

== Title ==

== Title ==

New Approximation Results for Resource Replication Problems

New Connections between Fixed-Parameter Algorithms and Approximation Algorithms

== Speaker ==

== Speaker ==

== Abstract ==

== Abstract ==

Traditionally fixed-parameter algorithms (FPT) and approximation algorithms have been considered as different approaches for dealing with NP-hard problem. The area of fixed-parameter approximation algorithms tries to tackle problems which are intractable to both these techniques. In this talk we will start with the formal definitions of fixed-parameter approximation algorithms and give a brief survey of known positive and negative results. Then (under standard conjectures in computational complexity) we show the first fixed-parameter inapproximability results for Clique and Set Cover, which are two of the most famous fixed-parameter intractable problems. On the positive side we obtain polynomial time f(OPT)-approximation algorithms for a number of W[1]-hard problems such as Minimum Edge Cover, Directed Steiner Forest, Directed Steiner Network, etc. Finally we give a natural problem which is W[1]-hard, does not have a constant factor approximation in polynomial time but admits a constant factor FPT-approximation.

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  

versions of the problem.

This is joint work with Samir Khuller and Barna Saha.

This is joint work with MohammadTaghi Hajiaghayi and Guy Kortsarz.