STRUCT-APPROX

NP-nehéz kombinatorikus optimalizálási problémák polinom időben történő approximálhatóságát vizsgáljuk. Ebben az irányban új eredményeink főként gráfoknak olyan csúcspartícióira vonatkoznak, amelyekben az egyes csúcsoknak a saját osztályukba eső szomszédaik számára adottak előírások (alsó korlátok).

Résztvevő intézmény: LAMSADE, Université Paris-Dauphine (http://www.lamsade.dauphine.fr/)