Name
Abstract | ||
|---|---|---|
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). |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0166-218X(98)00104-8 | Discrete Applied Mathematics |
Keywords | Field | DocType |
stacker-crane problem,data-dependent bounds,worst-case analysis,asymmetric stacker-crane problem,triangle inequality | Graph theory,Discrete mathematics,Approximation algorithm,Combinatorics,Hamiltonian path,Directed graph,Mixed graph,Triangle inequality,Digraph,Mathematics,Traverse | Journal |
Volume | Issue | ISSN |
91 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
2 | 0.40 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Giovanni Righini | 1 | 520 | 33.90 |
| Marco Trubian | 2 | 594 | 51.20 |