Xianghui Zhong

activity

20182021

most citedHard to Solve Instances of the Euclidean Traveling Salesman Problem

23 citations · 33 across the 8 of their papers we have counts for

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2021★ 4 cited

The Approximation Ratio of the $k$ -Opt Heuristic for the Euclidean Traveling Salesman Problem

Ulrich A. Brodowsky, Stefan Hougardy, Xianghui Zhong

The $k$ -Opt heuristic is a simple improvement heuristic for the Traveling Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces $k$ edges of the tour by $…

cs.DS2020★ 1 cited

Slightly Improved Upper Bound on the Integrality Ratio for the $s - t$ Path TSP

Xianghui Zhong

In this paper we investigate the integrality ratio of the standard LP relaxation for the metric $s - t$ Path TSP. We make a near-optimal choice for an auxiliary function used in the…

The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem

Slightly Improved Upper Bound on the Integrality Ratio for the s−t Path TSP

The Approximation Ratio of the $k$ -Opt Heuristic for the Euclidean Traveling Salesman Problem

Slightly Improved Upper Bound on the Integrality Ratio for the $s - t$ Path TSP