A polynomial combinatorial algorithm for generalized minimum cost flow

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A polynomial combinatorial algorithm for generalized minimum cost flow

Full text

Pdf (705 KB)

Source

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

Atlanta, Georgia, United States

Pages: 11 - 18

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Kevin D. Wayne

Computer Science Department, Princeton University, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 52, Citation Count: 6

Additional Information:

references cited by 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/301250.301261 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	Proceedings of the IOth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999.
	2	Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	3	Bengt Ingemar Aspvall, Efficient algorithms for certain satisfiability and linear programming problems, 1981
	4	B. Aspvall and Y. Shiloach. A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM Journal on Computing, 9:827-845, 1980.
	5	R. Barahona , E. Tardos, Note on Weintraub's minimum-cost circulation algorithm, SIAM Journal on Computing, v.18 n.3, p.579-583, June 1989 [doi>10.1137/0218039]
	6	Edith Cohen , Nimrod Megiddo, Improved Algorithms for Linear Inequalities with Two Variables per Inequality, SIAM Journal on Computing, v.23 n.6, p.1313-1350, Dec. 1994 [doi>10.1137/S0097539791256325]
	7	Edith Cohen , Nimrod Megiddo, New algorithms for generalized network flows, Mathematical Programming: Series A and B, v.64 n.3, p.325-336, May 11, 1994 [doi>10.1007/BF01582579]
	8	G. B. Dantzig. Linear programming and extensions. Princeton University Press, Princeton, N J, I962.
	9	F. Clover, J. Hultz, D. Klingman, and J. Stutz. Generalized networks: A fundamental computer based planning tool. Management Science, 24:1209-1220, 1978.
	10	F. Glover, D. Klingman, and N. Phillips. Netform modeling and applications. Interfaces, 20:7- 27, 1990.
	11	Andrew V. Goldberg , Serge A. Plotkin , Éva Tardos, Combinatorial algorithms for the generalized circulation problem, Mathematics of Operations Research, v.16 n.2, p.351-381, May 1991 [doi>10.1287/moor.16.2.351]
	12	A. V. Goldberg and S. Rao. Length functions for flow computations. Technical Report 97-055, NEC Research Institute, 1997.
	13	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by canceling negative cycles, Journal of the ACM (JACM), v.36 n.4, p.873-886, Oct. 1989 [doi>10.1145/76359.76368]
	14	D. Goldfarb and Z. Jin. A polynomial dual simplex algorithm for the generalized circulation problem. Technical report, Department of Industrial Engineering and Operations Research, Columbia University, 1995.
	15	Donald Goldfarb , Zhiying Jin, A faster combinatorial algorithm for the generalized circulation problem, Mathematics of Operations Research, v.21 n.3, p.529-539, Aug. 1996 [doi>10.1287/moor.21.3.529]
	16	D. Goldfarb, Z. Jin, and Y. Lin. A polynomial dual simplex algorithm for the generalized circulation problem. Technical report, Department of Industrial Engineering and Operations Research, Columbia University, 1998.
	17	Donald Goldfarb , Zhiying Jin , James B. Orlin, Polynomial-time highest-gain augmenting path algorithms for the generalized circulation problem, Mathematics of Operations Research, v.22 n.4, p.793-802, Nov. 1997 [doi>10.1287/moor.22.4.793]
	18	Dorit S. Hochbaum , Nimrod Megiddo , Joseph (Seffi) Naor , Arie Tamir, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, Mathematical Programming: Series A and B, v.62 n.1, p.69-83, Oct. 21, 1993 [doi>10.1007/BF01585160]
	19	Dorit S. Hochbaum, Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality, SIAM Journal on Computing, v.23 n.6, p.1179-1192, Dec. 1994 [doi>10.1137/S0097539793251876]
	20	W. S. Jewetl. Optimal flow through networks with gains. Operations Research, 10:476-499, 1962.
	21	L. V. Kantorovich. Mathematical methods of organizing and planning production. Publication House of the Leningrad State University, page 68, 1939. Translated in Management Science, 6:366- 422, I960.
	22	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	23	L. G. Khachiyan. Polynomial algorithms in linear programming. Zh. Vychisl. Mat. Mat. Fiz., 20:53- 72, 1980.
	24	M. Klein. A primal method for minimal cost flows with applications to the assignment and and transportation problems. Management Science, 14:205- 220, I967.
	25	S. T. McCormick and A. Shioura. Minimum ratio canceling is polynomia~ for linear programming, but not strongly polynomial, even for networks. Manuscript, i999.
	26	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	27	N. Megiddo. Toward a genuinely polynomial algorithm for linear programming. SIAM Journal on Computing, 12:347-353, 1983.
	28	Jeffrey D. Oldham, Combinatorial approximation algorithms for generalized flow problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.704-714, January 17-19, 1999, Baltimore, Maryland, United States
	29	Terri L. Griffith , Mark A. Fuller , Gregory B. Northcraft , Tomasz Radzik, Faster Algorithms for the Generalized Network Flow Problem, Mathematics of Operations Research, v.23 n.1, p.69-100, January 1998 [doi>10.1287/moor.23.1.69]
	30	Andreas S. Schulz , Robert Weismantel, An oracle-polynomial time augmentation algorithm for integer programming, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.967-968, January 17-19, 1999, Baltimore, Maryland, United States
	31	M. Shigeno, S. Iwata, and S. T. McCormick. Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow. 1998.
	32	Robert Shostak, Deciding Linear Inequalities by Computing Loop Residues, Journal of the ACM (JACM), v.28 n.4, p.769-779, Oct. 1981 [doi>10.1145/322276.322288]
	33	Éva Tardos , Kevin D. Wayne, Simple Generalized Maximum Flow Algorithms, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.310-324, June 22-24, 1998
	34	P. M. Vaidya. Speeding up linear programming using fast matrix multiplication. In 30th Annual IEEE Symposium on Foundations o/Computer Science, pages 332-337, 1989.
	35	C. Wallacher. A generalization of the minimummean cycle selection rule in cycle canceling algorithms. Technical report, Inst. Fiir Ang. Math., Braunschweig, Germany, 1991.
	36	C. Wallacher and U. T. Zimmermann. A polynomial cycle canceling algorithm for submodular flows. Manuscript, 1997.
	37	Kevin Daniel Wayne , Eva Tardos, Generalized maximum flow algorithms, 1999
	38	Kevin D. Wayne , Lisa Fleischer, Faster approximation algorithms for generalized flow, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.981-982, January 17-19, 1999, Baltimore, Maryland, United States
	39	A. Weintraub. A primal algorithm to solve network flow problems with convex costs. Management Science, 21:87-97, 1974.

CITED BY 6

	S. Thomas McCormick , Akiyoshi Shioura, Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.944-952, January 09-11, 2000, San Francisco, California, United States
	Andreas S. Schulz , Robert Weismantel, The Complexity of Generic Primal Algorithms for Solving General Integer Programs, Mathematics of Operations Research, v.27 n.4, p.681-692, November 2002
	Omid Madani, On policy iteration as a Newton's method and polynomial policy iteration algorithms, Eighteenth national conference on Artificial intelligence, p.273-278, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Ravindra K. Ahuja , Özlem Ergun , James B. Orlin , Abraham P. Punnen, A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics, v.123 n.1-3, p.75-102, 15 November 2002
	Tomasz Radzik, Improving time bounds on maximum generalised flow computations by contracting the network, Theoretical Computer Science, v.312 n.1, p.75-97, 26 January 2004
	Jieyi Long , Ja Chun Ku , Seda Ogrenci Memik , Yehea Ismail, A self-adjusting clock tree architecture to cope with temperature variations, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California