• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >A local search algorithm for binary maximum 2-path partitioning
【24h】

A local search algorithm for binary maximum 2-path partitioning

机译：二进制最大2路径分区的本地搜索算法

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

摘要

Let G be a complete (undirected) graph with 3l vertices. Given a binary weight function on the edges of G, the binary maximum 2-path partitioning problem is to compute a set of l vertex-disjoint simple 2-edge paths with maximum total edge weight. The problem is NP-hard(Garey and Johnson 1979) [1]. In this paper we propose a simple local search algorithm with polynomial running time for the problem and analyze its performance for several search depths. For depth 2, we show that the algorithm is a 0.3333-approximation, and that the bound is tight. For depth 3, we show that the algorithm is a 0.4-approximation. For depth 9, we show that the algorithm is a 0.55-approximation, improving on the best-known 0.5265 bound for the problem. We also consider the special case where G is subcubic, that is, the maximum degree in its subgraph induced by the unit-weight edges is 3. In this case we show that the algorithm is a 0.375-approximation for depth 2 and a 0.5-approximation for depth 3. In addition, we show that depth 7 is sufficient for the 0.55 bound guarantee. Finally we give, by means of bad instances, upper bounds on the performance guarantees of the algorithm. For depth 2 we show a 0.4 upper bound in the subcubic case. For depth 3 we show a 0.6 upper bound, as well as a 0.7 upper bound in the subcubic case. For the general (non-negative) weight problem we show a 0.5556 upper bound for depth 3 (for depth 2, the tight 0.3333 ratio holds for this problem as well).
机译：令G为具有3l个顶点的完整（无向）图。给定G边缘的二进制权重函数，二进制最大2路径分区问题将计算一组具有最大总边缘权重的l个顶点不相交的简单2边缘路径。问题是NP难的（Garey and Johnson 1979）[1]。在本文中，我们提出了一个简单的具有多项式运行时间的局部搜索算法来解决该问题，并分析了其在多种搜索深度下的性能。对于深度2，我们证明该算法为0.3333逼近，并且边界是紧密的。对于深度3，我们表明该算法为0.4逼近。对于深度9，我们证明了该算法为0.55近似值，对问题的最著名的0.5265进行了改进。我们还考虑了特殊情况，其中G是次三次的，即其子图中由单位权重边缘引起的最大度为3。在这种情况下，我们表明算法对于深度2为0.375近似，而对于深度2为0.5-深度3的近似值。此外，我们证明深度7足以满足0.55的边界保证。最后，通过不良实例，给出了算法性能保证的上限。对于深度2，我们在次立方情况下显示了0.4的上限。对于深度3，我们显示了0.6的上限，在亚三次情况下显示了0.7的上限。对于一般的（非负）重量问题，我们为深度3显示了0.5556的上限（对于深度2，该问题的紧密0.3333比率也成立）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号