On approximating multi-criteria TSP

Manthey, Bodo (2012) On approximating multi-criteria TSP. ACM Transactions on Algorithms, 8 (2). p. 17. ISSN 1549-6325

PDF
Restricted to UT campus only: Request a copy
412Kb

Abstract:	We present approximation algorithms for almost all variants of the multicriteria traveling salesman problem (TSP). First, we devise randomized approximation algorithms for multicriteria maximum traveling salesman problems (Max-TSP). For multicriteria Max-STSP where the edge weights have to be symmetric, we devise an algorithm with an approximation ratio of 2/3 $-\varepsilon.$ For multicriteria Max-ATSP where the edge weights may be asymmetric, we present an algorithm with a ratio of 1/2 $-\varepsilon.$ Our algorithms work for any fixed number k of objectives. Furthermore, we present a deterministic algorithm for bicriteria Max-STSP that achieves an approximation ratio of 7/27. Finally, we present a randomized approximation algorithm for the asymmetric multicriteria minimum TSP with triangle inequality (Min-ATSP). This algorithm achieves a ratio of log $n + \varepsilon.$
Item Type:	Article
Copyright:	© 2012 ACM
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/80244
Official URL:	http://dx.doi.org/10.1145/2151171.2151180
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page