23 citations · 33 across the 8 of their papers we have counts for
8 papers
The Approximation Ratio of the -Opt Heuristic for the Euclidean Traveling Salesman Problem
Ulrich A. Brodowsky, Stefan Hougardy, Xianghui Zhong
The -Opt heuristic is a simple improvement heuristic for the Traveling Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces edges of the tour by $…
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…
On the Approximation Ratio of the -Opt and Lin-Kernighan Algorithm
Xianghui Zhong
The -Opt and Lin-Kernighan algorithm are two of the most important local search approaches for the Metric TSP. Both start with an arbitrary tour and make local improvements in e…
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…
Probabilistic Analysis of Edge Elimination for Euclidean TSP
Xianghui Zhong
One way to speed up the calculation of optimal TSP tours in practice is eliminating edges that are certainly not in the optimal tour as a preprocessing step. In order to do so seve…
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…