Deterministic algorithms for multi-criteria TSP
Manthey, Bodo (2011) Deterministic algorithms for multi-criteria TSP. In: 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011, 23-25 May 2011, Tokyo, Japan.
Restricted to UT campus only: Request a copy
|Abstract:||We present deterministic approximation algorithms for the multi-criteria traveling salesman problem (TSP). Our algorithms are faster and simpler than the existing randomized algorithms.
First, we devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/2k − ε and 1/(4k − 2) − ε, respectively, where k is the number of objective functions. For two objective functions, we obtain ratios of 3/8 − ε and 1/4 − ε for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes.
Second, we adapt the generic cycle cover algorithm for Min-TSP. It achieves ratios of 3/2 + ε, , and for multi-criteria Min-ATSP with distances 1 and 2, Min-ATSP with -triangle inequality and Min-STSP with -triangle inequality, respectively.
|Item Type:||Conference or Workshop Item|
|Copyright:||© 2011 Springer|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/77041|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page