Research On Approximation Algorithm For Min-Max Cycle Cover Problem On A Mixed Graph

This paper focuses on the min-max cycle cover problem on a mixed graph.Depending on different objects that are asked to be covered,there are two specific cases:the first one is where the covered object is only the arc set,and the other one is where the covered object contains both arc set and edge set.This class of problems is an important combinatorial optimization problem in computer science and operations research,and it and its variants have a wide range of applications in related fields such as courier delivery,garbage collection,snow removal,etc.Therefore,Research on the problems has important theoretical value and practical significance.In this paper,we study the problems from the perspective of approximation algorithms,and give better approximation algorithms for each of the two cases.The first problem studied in this paper is the min-max cycle cover problem where the covered object is only arc set.The problem can be described as follows:we are given 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 with a weight,respectively.All weights are positive integers and satisfy the triangle inequality.Given a positive integer k,the requirement of the problem is to determine k tours such that these k tours can pass through all the arcs in A.The objective of the problem is to minimize the weight of the maximum weight tour.For this problem,we give an approximation algorithm with an approximation ratio of 37/5.The basic idea of the algorithm is as follows:First,a guess of the optimal value OPT for the instance,?,is given.Then,delete all the edges with weight greater than ?/2 in G and obtain several connected components.For each connected component,depending on the structure of G,design two candidate tours that cover all the arcs that fall on this component.Select the tour with the smaller weight and broke it into a number of paths using a tour-splitting algorithm.Connect the two endpoints of each path to create a number of sub-tours.Determining the total number of all the sub-tours,if it is less than or equal to k,which means that OPT ??,then the algorithm outputs these sub-tours,otherwise returns failure.Finally,since 2maxa?A w(a)?OPT ?2w(G)due to the triangle inequality,hence,a standard binary search can be applied in[2maxa?A w(a),2w(G)]to find the minimum value ?*such that a feasible solution with an objective value of no more than 37?*/5 can be constructed.By the definition of ?*,we know that OPT>?*-1,i.e.?*?OPT.Combining the above,we can obtain an approximation algorithm with an approximation ratio of 37/5.The second problem studied in this paper is the min-max cycle cover problem where the covered object contains both arcs and edges.The problem is a generalization of the first problem,and the difference between the two problems is the inputs and the requirements of the problems.The input of this problem adds a subset AR of the arc set A and a subset ER of the edge set E.The requirement of the problem is to find k tours such that these tours can be cover all the arcs in AR and all the edges in ER.The obj ective of the problem is still to minimize the weight of the maximum weight tour.In addition to designing three candidate tours in each connected component depending on the structure of G,we employ similar idea to that of the first problem and give an approximation algorithm with an approximation ratio of min{33/5,12+21?/2+3?},here?>0 is a constant related to the input graph G.