文献类型：期刊文献

英文题名：Approximation Algorithms for Some Min-Max and Minimum Stacker Crane Cover Problems

作者：Sun, Yuhui[1]; Yu, Wei[1]; Liu, Zhaohui[1]

机构：[1] School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2021

卷号：13135 LNCS

起止页码：400

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20215211403362)

基金：Acknowledgement. This research is supported by the National Natural Science Foundation of China under grant numbers 11671135, 11871213 and the Natural Science Foundation of Shanghai under grant number 19ZR1411800.

语种：英文

外文关键词：Cranes - Approximation algorithms - Graph theory

摘要：We study two stacker crane cover problems and their variants. 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 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 λ. 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 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 restricted case of the SCC problem with symmetric arc weights. If the arc weights are 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 we first propose a 4-approximation algorithm. ? 2021, Springer Nature Switzerland AG.