On dual minimum cost flow algorithms (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On dual minimum cost flow algorithms (extended abstract)

Full text

Pdf (945 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 117 - 125

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Jens Vygen

Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, 53113 Bonn, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 51, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335319 What is a DOI?

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	R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows. Prentice-Hall, Englewood Cliffs, 1993
	2	Ronald D. Armstrong , Zhiying Jin, A new strongly polynomial dual network simplex algorithm, Mathematical Programming: Series A and B, v.78 n.2, p.131-148, Aug. 1, 1997 [doi>10.1007/BF02614366]
	3	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	4	Thomas R. Ervolina , S. Thomas McCormick, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Discrete Applied Mathematics, v.46 n.2, p.133-165, Oct. 12, 1993 [doi>10.1016/0166-218X(93)90025-J]
	5	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	6	Harold N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, v.31 n.2, p.148-168, Sept. 1985 [doi>10.1016/0022-0000(85)90039-X]
	7	R. Hassin. The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm. Mathematical Programming 25 (1983), 228-239
	8	B. Korte, J. Vygen. Combinatorial Optimization: The. ory and Algorithms. Springer, Berlin, 2000
	9	James B. Orlin, A faster strongly polynomial minimum cost flow algorithm, Operations Research, v.41 n.2, p.338-350, March–April 1993 [doi>10.1287/opre.41.2.338]
	10	James B. Orlin , Serge A. Plotkin , Éva Tardos, Polynomial dual network simplex algorithms, Mathematical Programming: Series A and B, v.60 n.3, p.255-276, July 19, 1993 [doi>10.1007/BF01580615]
	11	Serge A. Plotkin , Éva Tardos, Improved dual network simplex, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.367-376, January 22-24, 1990, San Francisco, California, United States
	12	M. Shigeno, S. Iwata, and S.T. McCormick. Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow. Manuscript
	13	Éva Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, v.5 n.3, p.247-255, 1985 [doi>10.1007/BF02579369]