Parameterized Approximation Schemes using Graph Widths
Michael Lampis
Kyoto University, Japan
Kyoto University, Japan
2014/05/13 Tuesday 4PM-5PM
Room 1409
Room 1409
A number of natural graph problems are known to be W-hard to solve exactly when parameterized by standard widths (treewidth or clique-width). At the same time, such problems are typically hard to approximate in polynomial time. In this talk we will present a natural randomized rounding technique that extends well-known ideas and can be used to obtain FPT approximation schemes for several such problems, evading both polynomial-time inapproximability and parameterized intractability bounds.