Approximating Multi-Criteria Max-TSP

Markus Bläser, Bodo Manthey, Oliver Putz

Abstract

We present randomized approximation algorithms for multi-criteria Max-TSP. For Max-STSP with k > 1 objective functions, we obtain an approximation ratio of $1/k - \eps$ for arbitrarily small $\eps > 0$. For Max-ATSP with k objective functions, we obtain an approximation ratio of $1/(k+1) - \eps$.
BibTeX
@inproceedings{blaser2008approximating,
  author = {Markus Bläser and Bodo Manthey and Oliver Putz},
  title = {{Approximating Multi-Criteria Max-TSP}},
  booktitle = {ESA},
  year = {2008},
  url = {https://openreview.net/forum?id=ORTBLmNQSq},
}

Loading related content...

Figure