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

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

Abstract

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

CLC Number:

O223

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2021.01.010

https://www.ort.shu.edu.cn/EN/Y2021/V25/I1/107

Figures/Tables 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]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[2]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[3]	Ziyan CHEN, Yun QIAO, Yi WANG. Mixed graphs with negative inertia index 1 [J]. Operations Research Transactions, 2024, 28(4): 152-161.
[4]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[5]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[6]	Bing SU, Wyatt CARLSON, Jiabin FAN, Arthur GAO, Yanjun SHAO, Guohui LIN. Sharing bicycle relocating with minimum carbon emission [J]. Operations Research Transactions, 2022, 26(3): 75-91.
[7]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[8]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[9]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[10]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[11]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[12]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[13]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[14]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[15]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

Related Articles 15

Recommended Articles

Metrics

Comments