K-TSP问题的近似算法

• 作者: 刘方池 王德荣
• 来源期刊: 华中理工大学学报
• 学科: 数学
• 关键词: K-TSP 近似解 最优解 权函数变换
• 年，卷（期）: 2000,（8）
• 页码范围: 72-73,76
• 页数: 3页
• 分类号: O221
• 字数: 1715字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2000.08.027

摘要

利用△TSP问题的Christofides算法及其在K-TSP问题上的扩展,通过权函数变换c'ij=cij-ui-vj使c'ij>0, c'ik+c'kj≥c'ij,给出了求解K-TSP问题的有效途径,得到了目标函数的更好的界值估计,C(Ha)≤λ(n)C(H*)-(λ(n)-1)(X).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王德荣	华中理工大学数学系	2	9	1.0	2.0
2	刘方池	华中理工大学经济学院	3	9	1.0	3.0