Name
Abstract | ||
|---|---|---|
We present approximation algorithms for almost all variants of the multi- criteria traveling salesman problem (TSP), whose performances are independent of the number k 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 2/3 ". For multi-criteria Max-ATSP, where the edge weights may be asymmetric, we present an algorithm with an approximation ratio of 1/2 ". Our algorithms work for any fixed number k 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 2/3 and 1/2, respectively, of the weight of a cycle cover. Furthermore, we present a deterministic algorithm for bi-criteria Max-STSP that achieves an approximation ratio of 61/243 � 1/4. 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 log n + ". 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 1/(1 ) + ". |
Year | DOI | Venue |
|---|---|---|
2009 | 10.4230/LIPIcs.STACS.2009.1853 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
traveling salesman,multi-criteria optimization.,approximation algorithms,traveling salesman problem,objective function,data structure,triangle inequality | Approximation algorithm,Discrete mathematics,Combinatorics,Minimax approximation algorithm,Multi-objective optimization,Travelling salesman problem,Christofides algorithm,Deterministic algorithm,Triangle inequality,Polynomial-time approximation scheme,Mathematics | Conference |
Citations | PageRank | References |
8 | 0.58 | 14 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bodo Manthey | 1 | 63 | 5.38 |