Working Seminar on Formal Models, Discrete Structures, and Algorithms

Practical algorithms for minimum genus

Michael Lampis (Universite Paris Dauphine)

When: June 22, 3pm

Where: room C417


Traditionally, when we study approximation algorithms for NP-hard problems we only consider algorithms that run in polynomial time. On the other hand, when we study FPT or super-polynomial time algorithms we typically only consider algorithms that return optimal solutions. The limits of both approaches are now gradually becoming clearer, motivating the study of algorithms that trade time for approximation.

In this talk we will present a few new results in this direction. We will discuss a generic DP approach using standard graph widths that can yield efficient FPT approximation schemes for problems which are W-hard. In addition, we will discuss approximation algorithms that run in sub-exponential time and achieve non-trivial guarantees which cannot be achieved in polynomial time. Finally, we will sketch PCP-based arguments placing barriers on further progress.