35 citations · 75 across the 13 of their papers we have counts for
Showing 2014 · cs.DMShow all
3 papers · 2 filters
cs.DM2014
The Approximation Ratio of the Greedy Algorithm for the Metric Traveling Salesman Problem
Judith Brecklinghaus, Stefan Hougardy
We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is . Moreover, we prove that the same result also holds for graph…
cs.DM2014★ 2 cited
Edge Elimination in TSP Instances
Stefan Hougardy, Rasmus T. Schroeder
The Traveling Salesman Problem is one of the best studied NP-hard problems in combinatorial optimization. Powerful methods have been developed over the last 60 years to find optimu…
cs.DM2014
On the Integrality Ratio of the Subtour LP for Euclidean TSP
Stefan Hougardy
A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is . A well known family of graphic TSP instances achieves this lower bound asympto…