Name
Abstract | ||
|---|---|---|
Given an edge-weighted transportation network G and a list of transportation requests L, the Stacker Crane Problem is to find a minimum-cost tour for a server along the edges of G that serves all requests. The server has capacity one, and starts and stops at the same vertex. In this paper, we consider the case that the transportation network G is a tree, and that the requests are chosen randomly according to a certain class of probability distributions. We show that a polynomial time algorithm by Frederickson and Guan [J. Algorithms 15 (1993) 29-60], which guarantees a 4/3-approximation in the worst case, on almost all inputs finds a minimum-cost tour, along with a certificate of the optimality of its output. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.jalgor.2004.07.007 | Journal of Algorithms |
Keywords | Field | DocType |
edge-weighted transportation network,stacker crane problem,j. algorithms,transportation requests l,worst case,minimum-cost tour,polynomial time algorithm,certain class,transportation network g,probability distribution | Flow network,Discrete mathematics,Combinatorics,Heuristic,Vertex (geometry),Computer science,Probability distribution,Almost surely,Stacker,Time complexity,Certificate | Journal |
Volume | Issue | ISSN |
61 | 1 | 0196-6774 |
Citations | PageRank | References |
14 | 0.85 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Sven O. Krumke | 2 | 308 | 36.62 |
| Till Nierhoff | 3 | 107 | 12.76 |
| SO Krumke | 4 | 34 | 2.76 |