Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-008 | 8th August 2012 15:18

On Approximation Lower Bounds for TSP with Bounded Metrics

RSS-Feed

Abstract:

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 bounded metrics for the metric bound equal to 4.


Paper:

TR12-008 | 30th January 2012 15:30

On Approximation Lower Bounds for TSP with Bounded Metrics


Abstract:

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 bounded metrics for the metric bound equal to 4.



ISSN 1433-8092 | Imprint