Note on Upper Bounds for TSP Domination Number

G. Gutin, A. Koller, Anders Yeo

Research output: Contribution to journalArticlepeer-review

51 Downloads (Pure)


The domination number, domn(A, n), of a heuristic A for the Asymmetric TSP is the maximum integer d = d(n) such that, for every instance I of the Asymmetric TSP on n cities, A produces a tour T which is not worse than at least d tours in I including T itself. Two upper bounds on the domination number are proved.
Original languageEnglish
Pages (from-to)52-54
Number of pages3
JournalAlgorithmic Operations Research
Issue number1
Publication statusPublished - 2006

Cite this