13 citations · 17 across the 5 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013
Approximation Hardness of Graphic TSP on Cubic Graphs
Marek Karpinski, Richard Schmied
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…
cs.CC2013
New Inapproximability Bounds for TSP
Marek Karpinski, Michael Lampis, Richard Schmied
In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now know…