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