Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTI-CRITERIA TRAVELING SALESMAN PROBLEM:
Reports tagged with multi-criteria traveling salesman problem:
TR09-076 | 19th August 2009
Christian Glaßer, Christian Reitwießner, Maximilian Witek

#### Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman

Revisions: 1

We improve and derandomize the best known approximation algorithm for the two-criteria 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+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

ISSN 1433-8092 | Imprint