𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A strongly polynomial algorithm for the transportation problem

✍ Scribed by P. Kleinschmidt; H. Schannath

Publisher
Springer-Verlag
Year
1995
Tongue
English
Weight
777 KB
Volume
68
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A faster polynomial algorithm for the un
A faster polynomial algorithm for the unbalanced Hitchcock transportation problem
✍ Ulrich Brenner πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 320 KB

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk 2 (log n + k log k)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomialtime algorithm

A strongly polynomial algorithm for the
A strongly polynomial algorithm for the inverse shortest arborescence problem
✍ Hu Zhiquan; Liu Zhenhong πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 909 KB

In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is. given a directed graph G and a set of nonnegative costs on its arcs. we need to modify those costs as little as possible to ensure that T, a given (.I-arborescence of G, is the shortest one. It is

A strongly polynomial algorithm for the
A strongly polynomial algorithm for the uniform balanced network flow problem
✍ Maria Grazia ScutellΓ‘ πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 565 KB

## Several balanced optimization problems have been analysed in the literature. Here, the balanced network flow problem in the uniform case is studied, and it is shown that it can be solved by the Newton's approach in O(n' log3 n) max-flow computations. The key of the proof is an extension of Rad