Improved Approximation and Hardness Bounds for $\beta$-TSP
The traveling salesman problem (TSP) asks for a minimum-length Hamiltonian cycle in a complete weighted graph. Its approximability depends on the edge lengths: unrestricted instances admit no constant-factor approximation unless $\mathrm{P}=\mathrm{NP}$, metric instances admit Christofides'$3/2$-approximation, and fixe...