Approximating multi-criteria Max-TSP

Markus Bläser*, Bodo Manthey, Oliver Putz

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

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 - ε for arbitrarily small ε > 0. For Max-ATSP with k objective functions, we obtain a ratio of 1/k+1 - ε.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2008
Subtitle of host publication16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings
EditorsDan Halperin, Kurt Mehlhorn
PublisherSpringer
Pages185-197
Number of pages13
ISBN (Electronic)978-3-540-87744-8
ISBN (Print)978-3-540-87743-1
DOIs
Publication statusPublished - 24 Dec 2008
Externally publishedYes
Event16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany
Duration: 15 Sep 200817 Sep 2008

Publication series

NameLecture Notes in Computer Science
Volume5193
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th Annual European Symposium on Algorithms, ESA 2008
CountryGermany
CityKarlsruhe
Period15/09/0817/09/08

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

  • Cite this

    Bläser, M., Manthey, B., & Putz, O. (2008). Approximating multi-criteria Max-TSP. In D. Halperin, & K. Mehlhorn (Eds.), Algorithms - ESA 2008: 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings (pp. 185-197). (Lecture Notes in Computer Science; Vol. 5193). Springer. https://doi.org/10.1007/978-3-540-87744-8_16