TY - JOUR
T1 - Approximation algorithms for multi-criteria traveling salesman problems
AU - Manthey, Bodo
AU - Shankar Ram, L.
PY - 2009/1
Y1 - 2009/1
N2 - We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of min{1+γ,2γ2/2γ2−2γ+1}+ε and a randomized approximation algorithm that achieves a ratio of 2γ3+2γ2/3γ2−2γ+1+ε. In particular, we obtain a 2+ε approximation for multi-criteria metric STSP.Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with γ-triangle inequality (ratio 1+γ/1+3γ−4γ2+ε), asymmetric TSP (ATSP) with γ-triangle inequality (ratio 1/2+γ3/1−3γ2+ε ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2).
AB - We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of min{1+γ,2γ2/2γ2−2γ+1}+ε and a randomized approximation algorithm that achieves a ratio of 2γ3+2γ2/3γ2−2γ+1+ε. In particular, we obtain a 2+ε approximation for multi-criteria metric STSP.Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with γ-triangle inequality (ratio 1+γ/1+3γ−4γ2+ε), asymmetric TSP (ATSP) with γ-triangle inequality (ratio 1/2+γ3/1−3γ2+ε ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2).
KW - Approximation algorithms
KW - Multi-criteria optimization
KW - Traveling salesman problem
U2 - 10.1007/s00453-007-9011-z
DO - 10.1007/s00453-007-9011-z
M3 - Article
SN - 0178-4617
VL - 53
SP - 69
EP - 88
JO - Algorithmica
JF - Algorithmica
IS - 1
ER -