Data-dependent bounds for the general and the asymmetric stacker–crane problems

The Stacker–Crane Problem (SCP) is a sequencing problem, arising in scheduling and transportation, that consists of finding the minimum cost cycle on a mixed graph with oriented arcs and unoriented edges: feasible solutions must traverse all the arcs. Approximation algorithms are known to provide a fixed worst-case bound if the triangle inequality holds. We consider the worst-case performance of approximation algorithms for the SCP when the triangle inequality can be violated (General SCP) and for a similar problem formulated on a complete digraph (Asymmetric SCP).