Speaker: Johan Nilsson
Title: Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth

Abstract: In this talk we present two novel generic schemes for approximation algorithms for optimization NP-hard graph problems constrained to partial k-trees. Our first scheme yields deterministic polynomial-time algorithms achieving typically an approximation factor of k/log^(1-epsilon) n for k = polylog (n).

The second scheme yields randomized polynomial-time algorithms achieving an approximation factor of k/log n, where k is superlogarithmic. Both our approximation methods lead to the best known approximation guarantees for some basic optimization problems. In particular, we obtain best known polynomial-time approximation guarantees for the classical maximum independent set problem in partial trees.

Joint work with Artur Czumaj (New Jersey Institute of Technology) and Andrzej Lingas (Lund University).

Back to the Summer School Website: [html]