Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with ATSP Problem:
TR12-008 | 30th January 2012
Marek Karpinski, Richard Schmied

On Approximation Lower Bounds for TSP with Bounded Metrics

Revisions: 1

We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>>

ISSN 1433-8092 | Imprint