文献类型：期刊文献

英文题名：Approximation algorithms for some min-max and minimum stacker crane cover problems

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

机构：[1]East China Univ Sci & Technol, Sch Math, 130 Meilong Rd, Shanghai 200237, Peoples R China

年份：2023

卷号：45

期号：1

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录：;EI(收录号：20224813175628);WOS:【SCI-EXPANDED(收录号:WOS:000889065800001)】；

基金：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.

语种：英文

外文关键词：Approximation algorithm; Stacker crane problem; Rural postman problem; Traveling salesman problem; Stacker crane cover

摘要：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 (SCCP) 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 (MSCCP) is to cover all the arcs in A by a minimum number of closed walks of weight at most The min-max stacker crane walk cover problem (SCWCP)/minimum stacker crane walk cover problem (MSCWCP) is a variant of the SCCP/MSCCP with closed walks replaced by (open) walks. For the SCCP with weakly symmetric arc weights, i.e. for every arc there exists 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 SCCP with weakly symmetric arc weights. If the arc weights are weakly symmetric, we devise the first constant-factor approximation algorithms for the SCWCP, the MSCCP and the MSCWCP with ratios 5, 5 7/2, and respectively. Finally, we first propose a 4-approximation algorithm for the (general) MSCWCP.