Multi-criteria TSP: Min and max combined


Manthey, Bodo (2012) Multi-criteria TSP: Min and max combined. Operations Research Letters, 40 (1). pp. 36-38. ISSN 0167-6377

[img] PDF
Restricted to UT campus only
: Request a copy
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$).
Item Type:Article
Copyright:© 2012 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page