Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Bounded Metrics:
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 >>>

TR13-066 | 25th April 2013
Marek Karpinski, Richard Schmied

Approximation Hardness of Graphic TSP on Cubic Graphs

We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>>

ISSN 1433-8092 | Imprint