Approximation Algorithms For Some Min-Max And Minimum Stacker Crane Cover Problems

With the development of information technology and Internet technology,modern logistics,unmanned driving technology and intelligent snow sweeping are becoming more and more important,which have also attracted the extensive attention of many scholars.Stacker Crane Problem(SCP)is an important combinatorial optimization problem in operations research.The SCP and its variants are widely used in logistics,transportation,urban service and other related fields.In this thesis,we study two stacker crane cover problems and their variants.For each problem,we design approximation algorithms that either are first proposed or improve on the previous results.Given a mixed graph G=(V,E,A)with vertex set V,edge set E and arc set A.Each edge or arc is associated with a nonnegative integer weight.The Min-Max Stacker Crane Cover Problem(SCC)aims to find at most k closed walks covering all the arcs in A such that the maximum weight of the closed walks is minimum.The Minimum Stacker Crane Cover Problem(MSCC)is to cover all the arcs in A by a minimum number of closed walks of length at most A.The Min-Max Stacker Crane Walk Cover Problem(SCWC)/Minimum Stacker Crane Walk Cover Problem(MSCWC)is a variant of the SCC/MSCC problem with closed walks replaced by(open)walks.For the SCC problem with weakly symmetric arc weights,i.e.for every arc there is a parallel edge of no greater weight,we obtain a 33/5-approximation algorithm.This improves on the previous 37/5-approximation algorithm for a special case of the weakly symmetric SCC problem.If the arc weights are weakly symmetric,we devise the first constant-factor approximation algorithms for the SCWC problem,the MSCC problem and the MSCWC problem with ratios 5,5 and 7/2,respectively.Finally,for the general MSCWC problem,i.e.the arc weights are not weakly symmetric,we first propose a 4-approximation algorithm.