Speaker: Gregory Gutin (Royal Holloway, University of London)

Title: A new classification of NP-hard combinatorial optimization problems

Abstract: 
---------
We use the notion of domination ratio introduced by Glover and Punnen in
1997 to present a new classification of combinatorial optimization (CO)
problems: DOM-easy and DOM-hard problems. It follows from results proved
already in the 1970's that {\tt min TSP} (both symmetric and asymmetric
versions) is DOM-easy. We prove that several CO problems are DOM-easy
including {\tt max $k$-SAT} and {\tt max cut}. We show that some other
problems, such as {\tt max clique} and {\tt min vertex cover}, are
DOM-hard unless P=NP.