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.
Citation
Tech. Report CSD-TR-04-01, Jan. 2004, Royal Holloway, University of London, UK.