Introduction to Domination Analysis
Gregory Gutin (gutincs.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.
Entry Submitted: 02/01/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|