Name
Title | ||
|---|---|---|
Transportation problems which can be solved by the use of hirsch-paths for the dual problems. |
Abstract | ||
|---|---|---|
Balinski uses his signature method for the proof of the Hirsch-conjecture for dual transportation polyhedra to obtain an efficient
algorithm for the assignment problem. We will show how to extend this method to other primal transportation problems, including
transportation problems with unit demands. We then prove that Balinski's assignment algorithm is equivalent, cycle by cycle,
to that of Hung and Rom. We demonstrate that, under some assumptions for our probability model, a modification of the latter
algorithm has an average complexity of O(n
2logn) and present some computational results confirming this. We also present results that indicate that this modification compares
favorably with Balinski's algorithm and other codes. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1007/BF02591692 | Math. Program. |
Keywords | Field | DocType |
dual problem,transportation problem,hirsch-conjecture.,assignment problem | Mathematical optimization,Probability model,Polyhedron,Transportation theory,Assignment problem,Hirsch conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
37 | 2 | 0025-5610 |
Citations | PageRank | References |
9 | 1.17 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Kleinschmidt | 1 | 9 | 1.17 |
| Carl W. Lee | 2 | 103 | 35.15 |
| Heinz Schannath | 3 | 9 | 1.17 |