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: $\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 … Read more