Difference between revisions of "CATS-Sep-27-2013"
(Created page with "== Title == New Connections between Fixed-Parameter Algorithms and Approximation Algorithms == Speaker == Rajesh Chitnis, University of Maryland == Abstract == Traditionally...") |
(→Title) |
||
| Line 1: | Line 1: | ||
== Title == | == Title == | ||
| − | + | List H-Coloring a Graph by Removing Few Vertices | |
== Speaker == | == Speaker == | ||
Revision as of 02:32, 25 August 2013
Title[edit]
List H-Coloring a Graph by Removing Few Vertices
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.
