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.
Citation
Tech. Report no. 10 Royal Holloway, Univ. of London, 2002.