Approximation Algorithms for the General and the Asymmetric Stacker-CraneProblems

摘要

The Stacker-Crane Problem (SCP) consists of finding the minimum lengthhamiltonian 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. The authors 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). They 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. They also discuss the relationship with the Asymmetric Traveling Salesman Problem (ATSP), and they derive sufficient (and meaningful) conditions for ATSP instances to be solvable within constant worst-case bounds equal to 3, 15/7 and 9/5.