Approximating multi-criteria Max-TSP

Markus Bläser, Bodo Manthey, Oliver Putz

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

Multi-criteria
Objective function
Approximation algorithms
Randomized Algorithms
Approximation Algorithms
Approximation

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
Bläser, Markus ; Manthey, Bodo ; Putz, Oliver. / Approximating multi-criteria Max-TSP. Algorithms - ESA 2008: 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings. editor / Dan Halperin ; Kurt Mehlhorn. Springer, 2008. pp. 185-197 (Lecture Notes in Computer Science).
@inproceedings{614cab033f47446e98c824ad42309875,
title = "Approximating multi-criteria Max-TSP",
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 - ε.",
author = "Markus Bl{\"a}ser and Bodo Manthey and Oliver Putz",
year = "2008",
month = "12",
day = "24",
doi = "10.1007/978-3-540-87744-8_16",
language = "English",
isbn = "978-3-540-87743-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "185--197",
editor = "Dan Halperin and Kurt Mehlhorn",
booktitle = "Algorithms - ESA 2008",

}

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. Lecture Notes in Computer Science, vol. 5193, Springer, pp. 185-197, 16th Annual European Symposium on Algorithms, ESA 2008, Karlsruhe, Germany, 15/09/08. https://doi.org/10.1007/978-3-540-87744-8_16

Approximating multi-criteria Max-TSP. / Bläser, Markus; Manthey, Bodo; Putz, Oliver.

Algorithms - ESA 2008: 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings. ed. / Dan Halperin; Kurt Mehlhorn. Springer, 2008. p. 185-197 (Lecture Notes in Computer Science; Vol. 5193).

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

TY - GEN

T1 - Approximating multi-criteria Max-TSP

AU - Bläser, Markus

AU - Manthey, Bodo

AU - Putz, Oliver

PY - 2008/12/24

Y1 - 2008/12/24

N2 - 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 - ε.

AB - 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 - ε.

U2 - 10.1007/978-3-540-87744-8_16

DO - 10.1007/978-3-540-87744-8_16

M3 - Conference contribution

SN - 978-3-540-87743-1

T3 - Lecture Notes in Computer Science

SP - 185

EP - 197

BT - Algorithms - ESA 2008

A2 - Halperin, Dan

A2 - Mehlhorn, Kurt

PB - Springer

ER -

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