Title: Polynomial approximation of NP-hard problems: the differential ratio
Speaker: Bruno Escoffier, Lamsade, University Paris Dauphine, France
Date: December 13, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Many well known combinatorial optimization problems are NP-hard, hence we cannot compute an optimal solution in polynomial time unless P=NP. In the polynomial approximation framework, one wants to devise algorithms which compute in polynomial time a feasible solution as good as possible. The most classical way to measure the quality of the solution A(I) outputed by the algorithm on instance I is to compute the ratio between the value of A(I) and the optimal value opt(I). We present in this talk the study of NP-hard optimization problems under a different approximation measure, called differential ratio, where we measure the quality of A(I) by looking at its relative position in the interval of feasible values [w(I),opt(I)] (w(I) denotes the value of the worst solution). We will give approximation results for particular problems (such as TSP or SAT) as well as structural results, in order to present the differences/similarities between the landscapes of standard and differential approximation.