Optimization Online


Domination Analysis of Combinatorial Optimization Problems.

Gregory Gutin (gutin***at***cs.rhul.ac.uk)
Alek Vainshtein (alek***at***cs.haifa.ac.il)
Anders Yeo (anders***at***cs.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society