# On approximating multi-criteria TSP

Manthey, Bodo (2009) On approximating multi-criteria TSP. In: 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, 26-28 Feb 2009, Freiburg, Germany (pp. pp. 637-648).

 Preview

236kB
 Abstract: We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number of criteria and come close to the approximation ratios obtained for TSP with a single objective function. We present randomized approximation algorithms for multi-criteria maximum traveling salesman problems (Max-TSP). For multi-criteria Max-STSP, where the edge weights have to be symmetric, we devise an algorithm that achieves an approximation ratio of . For multi-criteria Max-ATSP, where the edge weights may be asymmetric, we present an algorithm with an approximation ratio of . Our algorithms work for any fixed number of objectives. To get these ratios, we introduce a decomposition technique for cycle covers. These decompositions are optimal in the sense that no decomposition can always yield more than a fraction of and , respectively, of the weight of a cycle cover. Furthermore, we present a deterministic algorithm for bi-criteria Max-STSPthat achieves an approximation ratio of . Finally, we present a randomized approximation algorithm for the asymmetric multi-criteria minimum TSP with triangle inequality (Min-ATSP). This algorithm achieves a ratio of . For this variant of multi-criteria TSP, this is the first approximation algorithm we are aware of. If the distances fulfil the -triangle inequality, its ratio is . Item Type: Conference or Workshop Item Faculty: Electrical Engineering, Mathematics and Computer Science (EEMCS) Research Group: Link to this item: http://purl.utwente.nl/publications/68853 Organisation URL: urn:nbn:de:0030-drops-18537 Export this item as: BibTeXEndNoteHTML CitationReference Manager

Repository Staff Only: item control page