dc.creatorCorrea Haeussler, José
dc.creatorLarré, Omar
dc.creatorSoto San Martín, José
dc.date.accessioned2015-10-04T20:55:32Z
dc.date.available2015-10-04T20:55:32Z
dc.date.created2015-10-04T20:55:32Z
dc.date.issued2015
dc.identifierSIAM Journal on Discrete Mathematics, 29(2), 915–939. (25 pages)
dc.identifierDOI: 10.1137/140972925
dc.identifierhttps://repositorio.uchile.cl/handle/2250/134084
dc.description.abstractAfter a sequence of improvements Boyd et al. [TSP on cubic and subcubic graphs, Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6655, Springer, Heidelberg, 2011, pp. 65-77] proved that any 2-connected graph whose n vertices have degree 3, i.e., a cubic 2-connected graph, has a Hamiltonian tour of length at most (4/3)n, establishing in particular that the integrality gap of the subtour LP is at most 4/3 for cubic 2-connected graphs and matching the conjectured value of the famous 4/3 conjecture. In this paper we improve upon this result by designing an algorithm that finds a tour of length (4/3 - 1/61236)n, implying that cubic 2-connected graphs are among the few interesting classes of graphs for which the integrality gap of the subtour LP is strictly less than 4/3. With the previous result, and by considering an even smaller epsilon, we show that the integrality gap of the TSP relaxation is at most 4/3 - epsilon even if the graph is not 2-connected (i.e., for cubic connected graphs), implying that the approximability threshold of the TSP in cubic graphs is strictly below 4/3. Finally, using similar techniques we show, as an additional result, that every Barnette graph admits a tour of length at most (4/3 - 1/18)n.
dc.languageen
dc.publisherSociety for Industrial and Applied Mathematics
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Chile
dc.subjectTraveling salesman problem
dc.subjectCubic graphs
dc.subjectIntegrality gap
dc.titleTSP Tours in Cubic Graphs: Beyond 4/3 Read More: http://epubs.siam.org/doi/abs/10.1137/140972925
dc.typeArtículo de revista


Este ítem pertenece a la siguiente institución