On Approximating Multi-Criteria TSP

Details On Approximating Multi-Criteria TSP On Approximating Multi-Criteria TSP

2007-11-14

arxiv.org/abs/0711.2157v3

Computer Science

Data Structures and Algorithms

Preliminary version at STACS 2009. This paper is a revised full version, where some proofs are simplified

Scientific paper

We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP). First, we devise 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 with an approximation ratio of 2/3 - eps. For multi-criteria Max-ATSP, where the edge weights may be asymmetric, we present an algorithm with a ratio of 1/2 - eps. Our algorithms work for any fixed number k of objectives. Furthermore, we present a deterministic algorithm for bi-criteria Max-STSP that achieves an approximation ratio of 7/27. 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 + eps.

Affiliated with

Also associated with

No associations

Rating

On Approximating Multi-Criteria TSP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Approximating Multi-Criteria TSP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Approximating Multi-Criteria TSP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-530601