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

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.

Figures/Tables 2

References 9

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]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[2]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[5]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[6]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[7]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[8]	CHEN Guangting, CHEN Lei, ZHANG An, CHEN Yong. Approximation algorithms for two-machine flow shop scheduling with an outsourcing option [J]. Operations Research Transactions, 2016, 20(4): 109-114.
[9]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[10]	ZHANG Yuzhong, YANG Xiaoguang. The continuity properties of optimal value function of discrete optimization problems [J]. Operations Research Transactions, 2016, 20(3): 79-84.
[11]	SUN Ting, LI Gaidi, XU Wenqing. Approximation algorithms for max cut and max bisection problems using semi-definite programming relaxations [J]. Operations Research Transactions, 2016, 20(3): 21-32.
[12]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[13]	YAN Lincheng,XIAO Han,ZHAO Hongjuan,SUN Xiaoqi. An approximation algorithm for reliable facility location problem [J]. Operations Research Transactions, 2015, 19(4): 14-24.
[14]	GUAN Meigu. A historical review on the research and development [J]. Operations Research Transactions, 2015, 19(3): 1-7.
[15]	FAN Jing, ZHANG Feng. Supply chain scheduling problem with multiple unavailability intervals on a single machine [J]. Operations Research Transactions, 2015, 19(3): 116-122.

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

References 9

Related Articles 15

Recommended Articles

Metrics

Comments