Multi-criteria TSP: Min and max combined

Share/Save/Bookmark

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
208kB
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/79358
Official URL:http://dx.doi.org/10.1016/j.orl.2011.10.012
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page