Introduction to Domination Analysis

Gregory Gutin (gutincs.rhul.ac.uk)
Anders Yeo (anderscs.rhul.ac.uk)

Abstract: In the recently published book on the Traveling Salesman Problem, half of Chapter 6 is devoted to domination analysis (DA) of heuristics for the Traveling Salesman Problem. Another chapter (in preparation) is a detailed overview of the whole area of DA. Both chapters are of considerable length. The purpose of this paper is to give a short introduction to results and applications of DA. While we do not prove any significant new results, we provide proofs to a few extensions and improvements of previously known theorems. Some open problems are also raised.

Keywords: combinatorial optimization, domination analysis

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Tech. Report CSD-TR-04-01, Jan. 2004, Royal Holloway, University of London, UK.

Download: [PDF]

Entry Submitted: 02/01/2004
Entry Accepted: 02/01/2004
Entry Last Modified: 02/01/2004

Modify/Update this entry