Deterministic algorithms for multi-criteria Max-TSP

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
24 Downloads (Pure)

Abstract

We present deterministic approximation algorithms for the multi-criteria maximum traveling salesman problem (Max-TSP). Our algorithms are faster and simpler than the existing randomized algorithms. We devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/2k − $\varepsilon$ and 1/(4k−2) − $\varepsilon$, respectively, where k is the number of objective functions. For two objective functions, we obtain ratios of 3/8 − $\varepsilon$ and 1/4 − $\varepsilon$ for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes.
Original languageEnglish
Pages (from-to)2277-2285
Number of pages9
JournalDiscrete applied mathematics
Volume160
Issue number15
DOIs
Publication statusPublished - 2012

Keywords

  • Pareto optimization
  • Approximation algorithms
  • Traveling Salesman Problem
  • Multi-criteria optimization

Fingerprint Dive into the research topics of 'Deterministic algorithms for multi-criteria Max-TSP'. Together they form a unique fingerprint.

  • Cite this