Multi-criteria TSP: Min and max combined

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized. For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3,$3+\varepsilon$)-approximate Pareto curves. Here, the first parameter is the approximation ratio for the objectives that should be maximized, and the second parameter is the ratio for the objectives that should be minimized. For the asymmetric multi-criteria TSP (ATSP), we obtain an approximation performance of (1/2, $\log_2 n + \varepsilon$).
Original languageEnglish
Pages (from-to)36-38
Number of pages3
JournalOperations research letters
Volume40
Issue number1
DOIs
Publication statusPublished - 2012

Keywords

  • EWI-20664
  • Combinatorial optimization
  • Approximate Pareto curves
  • Approximation algorithms
  • IR-79358
  • Multi-criteria optimization
  • Traveling Salesman Problem
  • Pareto optimization
  • METIS-285205
  • Multi-criteria TSP

Fingerprint

Dive into the research topics of 'Multi-criteria TSP: Min and max combined'. Together they form a unique fingerprint.

Cite this