Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
We consider the travelling salesman problem (TSP) problem on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general. © 2004 Elsevier B.V. All rights reserved.
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
A.R. Gourlay, G. Kaye, et al.
Proceedings of SPIE 1989
Minghong Fang, Zifan Zhang, et al.
CCS 2024