|
 ABSTRACT
We present a new strongly polynomial algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of &Ogr;(n log n) shortest path problems on networks with n nodes and m arcs and runs in &Ogr;(n log n(m + n log n)) steps. Using a standard transformation, this approach yields an &Ogr;(m log n (m + n log n)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial algorithm due to Galil and Tardos, by a factor of m/n. Our algorithm is even more efficient if the number of arcs with finite upper bounds, say m', is much less than m. In this case, the number of shortest path problems solved is &Ogr;((m + n) log n).
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
AHUJA, R.K., GOLDBERG, A.V., ORLIN, J.B., AND TARJAN, R.E. Solving minimum cost flow problem by double scaling. To appear.
|
| |
2
|
BLAND, R.G., AND jENSEN, D.L. On the computational behavior of a polynomial-time network flow algorithm. Technical Report 661, School of Operations Research and industrial Engineering, Cornell University, Ithaca, 1985.
|
| |
3
|
COOK, S.A., AND RECKHOW, R.A. Time bounded random access machines. }. of Comput. System Sci. 7 (1973), 354-375.
|
| |
4
|
DIJKSTRA, E. A note of two problems in connexion with graphs. Numeriche Mathematics 1 (1959), 269-271.
|
 |
5
|
|
| |
6
|
FREDMAN, M.L., AND TARJAN, R.E., Fibonacci heaps and their uses in network optimization algorithms. 25th IEEE Syrup. on Found. of Comp, Sci. (1984), 338-346.
|
| |
7
|
|
| |
8
|
GALIL, Z., AND TARDOS, E. An O(n2 (m + n log n) log n) rain-cost flow algorithm. Proc. 27th Annual Symp. of Found. of Comp. Sci. (1986), 136-146.
|
| |
9
|
|
| |
10
|
|
| |
11
|
LAWLER, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.
|
| |
12
|
MEGIDDO, N. Towards a strongly polynomial algorithm for linear programming. SIAM j. of Computing 12(1983) 347-353.
|
| |
13
|
ORLIN, J.B. Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem. Technical Report No. 1615-84, Sloan School of Management, M.I.T., Cambridge, 1984.
|
| |
14
|
ROCK, H. Scating techniques for minimal cost network flows. In. V. Page, editor, Discrete Structures and Algorithms , Carl Hansen, Munich, 1980. pp 101-191.
|
| |
15
|
|
| |
16
|
|
CITED BY 36
|
|
Marios C. Papaefthymiou , Keith H. Randall, TIM: a timing package for two-phase, level-clocked circuitry, Proceedings of the 30th international conference on Design automation, p.497-502, June 14-18, 1993, Dallas, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X. Hu , R. G. Harber , S. C. Bass, Minimizing the number of delay buffers in the synchronization of pipelined systems, Proceedings of the 28th conference on ACM/IEEE design automation, p.758-763, June 17-22, 1991, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States
|
|
|
|
|
|
|
|
|
|
|
|
S. Gao , M. Kaufmann , F. M. Maley, Advances in homotopic layout compaction, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.273-282, June 18-21, 1989, Santa Fe, New Mexico, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2