Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MICHAEL LAMPIS:
All reports by Author Michael Lampis:

TR13-045 | 26th March 2013
Marek Karpinski, Michael Lampis, Richard Schmied

New Inapproximability Bounds for TSP

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>>




ISSN 1433-8092 | Imprint