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

G. Righini, M. Trubian

Research output: Book/ReportReportAcademic

82 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages50
Publication statusPublished - 1994

Publication series

NameMemorandum COSOR
Volume9420
ISSN (Print)0926-4493

Fingerprint Dive into the research topics of 'Approximation algorithms for the general and the asymmetric Stacker-Crane problems'. Together they form a unique fingerprint.

Cite this