...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of applied and industrial mathematics >Approximation algorithms for the maximum 2-peripatetic salesman problem
【24h】

Approximation algorithms for the maximum 2-peripatetic salesman problem

机译：最大2奇异推销员问题的近似算法。

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

摘要

Under study is the problem of finding two edge-disjoint Hamiltonian cycles (salesman routes) of maximal total weight in a complete undirected graph. For the case of edge weights from the interval [1, q], a polynomial algorithm is constructed with the guaranteed accuracy estimate 3q+2/4q+1. For the case of weights 1 and 2 and two different weight functions corresponding to the two routes, a polynomial algorithm with the accuracy estimate 11ρ-8/18ρ-15 is presented, where ρ is the accuracy estimate of an algorithm for solving a similar minimum optimization problem.
机译：在研究中的问题是在一个完整的无向图中找到两个最大总重的边不相交的哈密顿循环（推销员路线）。对于来自间隔[1，q]的边缘权重，构造了具有保证的精度估计值3q + 2 / 4q + 1的多项式算法。对于权重1和2以及对应于两条路线的两个不同权重函数的情况，提出了一种精度估计值为11ρ-8/18ρ-15的多项式算法，其中ρ是用于求解相似最小值的算法的精度估计优化问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号