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

doi:10.15960/j.cnki.issn.1007-6093.2021.01.010

运筹学学报 ›› 2021, Vol. 25 ›› Issue (1): 107-113.doi: 10.15960/j.cnki.issn.1007-6093.2021.01.010

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

包晓光¹, 路超¹, 黄冬梅²^,*(), 余炜³

1. 上海海洋大学信息学院, 上海 201306
2. 上海电力大学, 上海 200090
3. 华东理工大学理学院, 上海 200237

收稿日期:2020-01-02 出版日期:2021-03-15 发布日期:2021-03-05
通讯作者: 黄冬梅 E-mail:dmhuang@shou.edu.cn
作者简介:黄冬梅 E-mail: dmhuang@shou.edu.cn
基金资助:
国家自然科学基金(11701363);国家自然科学基金(41671431);上海市自然科学基金(19ZR1411800)

Approximation algorithm for min-max cycle cover problem on a mixed graph

Xiaoguang BAO¹, Chao LU¹, Dongmei HUANG²^,*(), Wei YU³

1. College of Information Technology, Shanghai Ocean University, Shanghai 201306, China
2. Shanghai University of Electric Power, Shanghai 200090, China
3. School of Science, East China University of Science and Technology, Shanghai 200237, China

Received:2020-01-02 Online:2021-03-15 Published:2021-03-05
Contact: Dongmei HUANG E-mail:dmhuang@shou.edu.cn

摘要/Abstract

摘要：

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

关键词: 近似算法, 混合图, 最小-最大, 圈覆盖, 乡村邮递员问题, 中国邮递员问题, 旅行商问题

Abstract:

We consider a min-max cycle cover problem, in which we are given a positive integer k and a mixed weighted graph G=(V, E, A) with vertex set V, edge set E and arc set A. Each edge in E and each arc in A is associated a weight, respectively. The problem is to determine k tours such that the k tours pass through all the arcs in A. The objective is to minimize the weight of the maximum weight tour. The problem is an important combinatorial optimization problem in operations research and computer science. This problem and its variants are widely used in related industries such as express delivery, trash collection, snow removal, etc. For the problem, we propose the first constant-factor approximation algorithm with ratio 37/5 by using binary search and tour splitting techniques.

Key words: approximation algorithm, mixed graph, min-max, cycle cover, rural postman problem, Chinese postman problem, traveling salesman problem

中图分类号:

O223

包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.

Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph[J]. Operations Research Transactions, 2021, 25(1): 107-113.

图/表 2

1	Frederickson G N , Hecht M S , Kim C E . Approximation algorithms for some routing problems[J]. Siam Journal on Computing, 1978, 7 (2): 178- 193. doi: 10.1137/0207017
2	Chyu C C . A mixed-strategy heuristic for the mixed arc routing problem[J]. Journal of the Chinese Institute of Industrial Engineers, 2001, 18 (3): 68- 76. doi: 10.1080/10170660109509459
3	Frederickson G N . Approximation algorithms for Some Postman Problems[J]. Journal of the ACM, 1979, 26 (3): 538- 554. doi: 10.1145/322139.322150
4	Arkin E M , Hassin R , Levin A . Approximations for minimum and min-max vehicle routing problems[J]. Journal of Algorithms, 2006, 59 (1): 1- 18. doi: 10.1016/j.jalgor.2005.01.007
5	管梅谷. 奇偶点图上作业法[J]. 数学学报, 1960, 10 (3): 263- 266.
6	Edmonds J , Johnson E L . Matching, Euler tours and the Chinese postman[J]. Mathematical Programming, 1973, 5 (1): 88- 124. doi: 10.1007/BF01580113
7	Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Pittsburgh: Graduate School of Industrial Administration, Carnegie-Mellon University, 1976.
8	Yu W , Liu Z H . Improved approximation algorithms for some min-max and minimum cycle cover problems[J]. Theoretical Computer Science, 2016, 654 (22): 45- 58.
9	Xu W Z , Liang W F , Lin X L . Approximation algorithms for min-max cycle cover problems[J]. IEEE Transactions on Computers, 2015, 64 (3): 600- 613. doi: 10.1109/TC.2013.2295609

[1]	吴弘一, 王冬, 万龙, 罗文昌. 嵌套加工型限制下的混合分批平行机排序问题的近似算法[J]. 运筹学学报（中英文）, 2026, 30(1): 188-196.
[2]	袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.
[3]	陈梓妍, 乔云, 汪毅. 负惯性指数为1的混合图[J]. 运筹学学报（中英文）, 2024, 28(4): 152-161.
[4]	高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.
[5]	袁藩, 徐大川, 张冬梅. k-均值问题的差分隐私算法综述[J]. 运筹学学报（中英文）, 2022, 26(3): 1-16.
[6]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[7]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[8]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[9]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[10]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[11]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报（中英文）, 2022, 26(1): 99-112.
[12]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报（中英文）, 2022, 26(1): 113-124.
[13]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[14]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[15]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.

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

Approximation algorithm for min-max cycle cover problem on a mixed graph

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

相关文章 15

编辑推荐

Metrics

本文评价