混合图上最小-最大圈覆盖问题的近似算法

• 作者: 包晓光 路超 黄冬梅 余炜
• 来源期刊: 运筹学学报
• 关键词: 近似算法 混合图 最小-最大 圈覆盖 乡村邮递员问题 中国邮递员问题 旅行商问题
• 年，卷（期）: 2021,（1）
• 页码范围: 107-113
• 页数: 7页
• 分类号: O223
• 语种: 中文
• DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.010

摘要

考虑一个混合图上的最小-最大圈覆盖问题.给定一个正整数k和一个混合加权图G=(V E,A),这里V表示顶点集,E表示边集,A表示弧集.E中的每条边和A中的每条弧关联一个权重.问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧.目标是极小化最大环游的权重.该问题是运筹学和计算机科学中一个重要的组合优化问题,它和它的变形在诸如快递配送、垃圾收集、积雪清扫等相关行业具有广泛应用.针对该问题,通过结合二分搜索和环游撕裂的技巧,首次给出了一个近似比为37/5的近似算法.