Approximation algorithms for some min–max and minimum stacker crane cover problems

We study two stacker crane cover problems and their variants. Given a mixed graph $$G=(V,E,A)$$ 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 $$\lambda $$ λ . 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 $$\frac{33}{5}$$ 33 5 -approximation algorithm. This improves on the previous $$\frac{37}{5}$$ 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 and $$\frac{7}{2}$$ 7 2 , respectively. Finally, we first propose a 4-approximation algorithm for the (general) MSCWCP.