Domination Analysis of Combinatorial Optimization Problems.

Gregory Gutin (gutincs.rhul.ac.uk)
Alek Vainshtein (alekcs.haifa.ac.il)
Anders Yeo (anderscs.rhul.ac.uk)

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.

Keywords: Combinatorial Optimization; Domination analysis; Approximation Algorithms; Heuristics

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Other )

Citation: Tech. Report no. 10 Royal Holloway, Univ. of London, 2002.

Download: [Postscript][PDF]

Entry Submitted: 11/14/2002
Entry Accepted: 11/14/2002
Entry Last Modified: 01/23/2003

Modify/Update this entry