Category: Seminars and Conferences
October 5th, 2010
Seminar of Prof. Vangelis Paschos, University of Paris-Dauphine.
Title: "Approximation by moderately exponential algorithms"
Sala Riunioni 1 (Meeting Room #1), DAUIN, third floor at 14h30
We present a trade-off between polynomial approximation and exact computation. We show how using ideas from both fields one can design approximation algorithms for several combinatorial problems achieving ratios that cannot be achieved in polynomial time