Multi-criteria TSP: Min and Max combined


Share/Save/Bookmark

Manthey, Bodo (2010) Multi-criteria TSP: Min and Max combined. In: 7th International Workshop Approximation and Online Algorithms, WAOA 2009, 10-11 September 2009, Copenhagen, Denmark.

[img]PDF
Restricted to UT campus only
: Request a copy
226Kb
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.
Item Type:Conference or Workshop Item
Copyright:© 2010 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74100
Official URL:http://dx.doi.org/10.1007/978-3-642-12450-1_19
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page