Difference between revisions of "CATS-Mar-08-2013"
| Line 1: | Line 1: | ||
== Title == | == Title == | ||
| − | New Approximation | + | New Connections between Fixed-Parameter Algorithms and Approximation Algorithms |
== Speaker == | == Speaker == | ||
| − | + | Rajesh Chitnis, University of Maryland | |
== 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. | |
| − | |||
| − | |||
| − | |||
| − | of | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | This is joint work with | + | This is joint work with MohammadTaghi Hajiaghayi and Guy Kortsarz. |
Latest revision as of 22:21, 27 February 2013
Title[edit]
New Connections between Fixed-Parameter Algorithms and Approximation Algorithms
Speaker[edit]
Rajesh Chitnis, University of Maryland
Abstract[edit]
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.
This is joint work with MohammadTaghi Hajiaghayi and Guy Kortsarz.
