Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman
Christian Glaer, Christian Reitwiener, Maximilian Witek · Electronic colloquium on computational complexity · 2009
We improve and derandomize the best known approximation algorithm for the twocriteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey. Moreover, we show that 2-TSP is randomized (3=2 + ; 2)-approximable, and we give the rst randomized approximations for the two-criteria traveling salesman path problems 2-TSPP, 2-TSPPs, and 2-TSPPst. We further provide arguments that indicate the hardness of improving our randomized approximation algorithms in the sense that such improvements force us to improve the best known approximations for TSP, TSPPs, and TSPPst (Christodes