• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Approximating Minimum-Cost Connected T-Joins
【24h】

Approximating Minimum-Cost Connected T-Joins

机译：近似最小成本的连接T型联接

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

摘要

We design and analyse approximation algorithms for the minimum-cost connected T-join problem: given an undirected graph G = (V, E) with nonnegative costs on the edges, and a set of nodes T is contained in V, find (if it exists) a spanning connected subgraph H of minimum cost such that T is the set of nodes of odd degree; H may have multiple copies of any edge of G. Recently, An, Kleinberg, and Shmoys (STOC 2012) improved on the long-standing 5/3 approximation guarantee for the s, t path TSP (the special case where T = {s, t}) and presented an algorithm based on LP rounding that achieves an approximation guarantee of 1+5~(1/2)/2 ≈ 1.618. We show that the methods of An et al. extend to the minimum-cost connected T-join problem to give an approximation guarantee of 5/3 - 1/(9|T|) + O (|T|~(-2)) when |T| ≥ 4; our approximation guarantee is 1.625 when |T| = 4, and it is ≈ 1.642 when |T| = 6. Finally, we focus on a prize-collecting version of the problem, and present a primal-dual algorithm that is "Lagrangian multiplier preserving" and that achieves an approximation guarantee of 3-2/(|T| - 1) when |T| ≥ 4.
机译：我们设计和分析了最小成本连接T形连接问题的近似算法：给定无向图G =（V，E），且边上具有非负成本，并且V中包含一组节点T，找到（如果它存在）最小成本的跨接子图H，使得T是奇数节点的集合； H可能具有G的任意边的多个副本。最近，An，Kleinberg和Shmoys（STOC 2012）对s，t路径TSP的长期5/3近似保证进行了改进（特殊情况下T = {s （t}），并提出了一种基于LP舍入的算法，该算法可实现1 + 5〜（1/2）/ 2≈1.618的近似保证。我们证明了An等人的方法。扩展到最小成本连接T形连接问题，当| T |达到5/3-1 /（9 | T |）+ O（| T |〜（-2））时≥4; | T |时，我们的近似保证为1.625。 = 4，并且| T |时约为≈1.642 =6。最后，我们将重点放在问题的奖金收集版本上，并提出一种原始对偶算法，即“保留拉格朗日乘数”，并且在以下情况下可实现3-2 /（|| T |-1）的近似保证。 | T | ≥4。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号