Approximation algorithms for the general and the asymmetric Stacker-Crane problems

The Stacker-Crane Problem (SCP) consists of finding the minimum length hamiltonian cycle on a mixed graph with oriented arcs and unoriented edges: feasible solutions must traverse all the arcs. Approximation algorithms are known for the case in which the triangle inequality holds. We consider the case in which the triangle inequality is violated (General SCP) and the case in which the problem is formulated on a complete digraph (Asymmetric SCP). We show how data-dependent worst-case bounds for the GSCP and the ASCP can be obtained by known approximation algorithms for the SCP with triangle inequality and by a new one. We also discuss the relationship with the Asymmetric Traveling Salesman Problem (ATSP) and we derive sufficient (and meaningful) conditions for ATSP instances to be solvable within constant worst-case bounds equal to 3, 15/7 and 9/5.