...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >TSP TOURS IN CUBIC GRAPHS: BEYOND 4/3
【24h】

TSP TOURS IN CUBIC GRAPHS: BEYOND 4/3

机译：立方图中的TSP旅游：超越4/3

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

After 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.
机译：经过一系列改进后，Boyd等[三次和次三次图上的TSP，整数编程和组合优化，计算机讲义。科学6655，Springer，Heidelberg，2011，pp。65-77]证明，任何2个连通图的n个顶点具有3度的度，即立方2连通图，其哈密顿量最大为（4/3） n，特别是确定对于三次2连通图，子行程LP的积分间隙最大为4/3，并且与著名的4/3猜想的猜想值匹配。在本文中，我们通过设计一种算法来改进此结果，该算法可以找到长度为（4/3-1/61236）n的行程，这表明三次2连通图是少数几个有趣类的图，其中，子行程LP严格小于4/3。根据先前的结果，并通过考虑甚至更小的epsilon，我们表明TSP弛豫的积分差距最大为4/3-epsilon，即使该图不是2连通的（即对于立方连通的图），这也意味着TSP在立方图中的逼近阈值严格低于4/3。最后，使用类似的技术，作为另外的结果，我们证明，每个Barnette图都允许最大长度为（4/3-1/18）n的行程。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号