1 citations · 1 across the 1 of their papers we have counts for
5 papers
On the Approximation Ratio of the 3-Opt Algorithm for the (1,2)-TSP
Xianghui Zhong
The (1,2)-TSP is a special case of the TSP where each edge has cost either 1 or 2. In this paper we give a lower bound of for the approximation ratio of the 2-Opt alg…
Lower Bounds on the Integraliy Ratio of the Subtour LP for the Traveling Salesman Problem
Xianghui Zhong
In this paper we investigate instances with high integrality ratio of the subtour LP. We develop a procedure to generate families of Euclidean TSP instances whose integrality ratio…
Slightly Improved Upper Bound on the Integrality Ratio for the Path TSP
Xianghui Zhong
In this paper we investigate the integrality ratio of the standard LP relaxation for the metric Path TSP. We make a near-optimal choice for an auxiliary function used in the…
The Approximation Ratio of the 2-Opt Heuristic for the Metric Traveling Salesman Problem
Stefan Hougardy, Fabian Zaiser, Xianghui Zhong
The 2-Opt heuristic is one of the simplest algorithms for finding good solutions to the metric Traveling Salesman Problem. It is the key ingredient to the well-known Lin-Kernighan…
Hard to Solve Instances of the Euclidean Traveling Salesman Problem
Stefan Hougardy, Xianghui Zhong
The well known conjecture states that the integrality ratio of the subtour LP is at most for metric Traveling Salesman instances. We present a family of Euclidean Trave…