STRUCT-APPROX
Polynomial-time approximability of NP-hard combinatorial optimization problems
We study the polynomial-time approximability of NP-hard combinatorial optimization problems. In this area, most of our recent results deal with vertex partitions of graphs, under local constraints that prescribe lower bounds on the number of neighbors of each vertex in its class.
Partner institution: LAMSADE, Université Paris-Dauphine (http://www.lamsade.dauphine.fr/)