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

Yuhui Sun (), Wei Yu () and Zhaohui Liu ()
Additional contact information
Yuhui Sun: East China University of Science and Technology
Wei Yu: East China University of Science and Technology
Zhaohui Liu: East China University of Science and Technology

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 29, 25 pages

Abstract: Abstract 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.

Keywords: Approximation algorithm; Stacker crane problem; Rural postman problem; Traveling salesman problem; Stacker crane cover (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00955-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00955-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00955-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().