运筹学学报 >
2021 , Vol. 25 >Issue 1: 107 - 113
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.01.010
混合图上最小-最大圈覆盖问题的近似算法
收稿日期: 2020-01-02
网络出版日期: 2021-03-05
基金资助
国家自然科学基金(11701363);国家自然科学基金(41671431);上海市自然科学基金(19ZR1411800)
Approximation algorithm for min-max cycle cover problem on a mixed graph
Received date: 2020-01-02
Online published: 2021-03-05
包晓光, 路超, 黄冬梅, 余炜 . 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021 , 25(1) : 107 -113 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.010
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.
| 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. |
| 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. |
| 3 | Frederickson G N . Approximation algorithms for Some Postman Problems[J]. Journal of the ACM, 1979, 26 (3): 538- 554. |
| 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. |
| 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. |
| 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. |
/
| 〈 |
|
〉 |