On the Integrality Gap of the Subtour LP for the 1,2-TSP

DOI10.1007/978-3-642-29344-3_51zbMath1354.90114OpenAlexW2747774057MaRDI QIDQ2894502

Frans Schalekamp, Anke van Zuylen, Jiawei Qian, David P. Williamson

Publication date: 29 June 2012

Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-29344-3_51

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (4)

New Approximation Algorithms for (1,2)-TSP ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ On the integrality ratio of the subtour LP for Euclidean TSP ⋮ Unnamed Item

This page was built for publication: On the Integrality Gap of the Subtour LP for the 1,2-TSP