@inproceedings{d88400519d53431f9afdd32c62580c65,
title = "Multi-criteria TSP: Min and Max combined",
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 − ε, 4 + ε) 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 present an algorithm that computes (1/2 − ε, log2 n + ε) approximate Pareto curves. In order to obtain these results, we simplify the existing approximation algorithms for multi-criteria Max-STSP and Max-ATSP. Finally, we give algorithms with improved ratios for some special cases.",
keywords = "IR-74100, EWI-16980, METIS-270700",
author = "Bodo Manthey",
note = "10.1007/978-3-642-12450-1_19 ; 7th International Workshop Approximation and Online Algorithms (WAOA 2009), Copenhagen, Denmark ; Conference date: 01-01-2010",
year = "2010",
doi = "10.1007/978-3-642-12450-1_19",
language = "Undefined",
isbn = "978-3-642-12450-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "205--216",
editor = "Evripidis Bampis and Klaus Jansen",
booktitle = "7th International Workshop Approximation and Online Algorithms (WAOA 2009)",
address = "Germany",
}