## Abstract

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γ

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}/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).Original language | English |
---|---|

Pages (from-to) | 69-88 |

Number of pages | 20 |

Journal | Algorithmica |

Volume | 53 |

Issue number | 1 |

DOIs | |

Publication status | Published - Jan 2009 |

## Keywords

- Approximation algorithms
- Multi-criteria optimization
- Traveling salesman problem