Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks

Full text

Pdf (754 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 944 - 952

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

S. Thomas McCormick	Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, BC, V6T 1Z2, Canada and SORIE at Cornell University
Akiyoshi Shioura	Department of Mechanical Engineering, Sophia University, 7-1 Kioi-cho, Chiyoda-ku, Tokyo 102-8554, Japan and Faculty of Commerce and Business Administration, University of British Columbia

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

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

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	Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	2	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]
	3	T. 1~. Ervolina and S. T. McCormick, "Canceling most helpful total cuts for minimum cost network flow," Networks 23, 41-52 (1993).
	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	M. GrStschel, L. Lov~sz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer- Verlag, Berlin (1988).
	6	Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
	7	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
	8	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]
	9	M. Hadjiat, "Un algorithme fortement polynomial pour la tension de cofit minimum bas6 sur les cocycles de cofits moyells minimums," Technical Report, Groupe intelligence Artificielle, Facult6 des Sciences de Lurainy, MarseiUe, France (1994). {In French.}
	10	R. Hassin, "The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm," Math. Programming 25, 228-239 (1983).
	11	M. Klein, "A primal method for minimal cost flows," Management Sci. 14, 205-220 (1967).
	12	Alexander V. Karzanov , S. Thomas McCormick, Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications, SIAM Journal on Computing, v.26 n.4, p.1245-1275, Aug. 1997 [doi>10.1137/S0097539794263695]
	13	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]
	14	M. Queyraane, "Theoretical efficiency of the algorithm 'Capacity' for the maximum flow problem," Math. Oper. Res. 5, 258-266 (1980).
	15	T. Ra~ik, "Parametric flows, weighted means of cuts, and fractional combinatorial optimization," in: P. Pardalos (ed.), Complexity in Numerical Optimization, World Scientific, 351-386 (1993).
	16	R. T. Rockafellar, Network Flows and Monotropic Optimization, John Wiley & Sons (1984).
	17	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	18	Maiko Shigeno , Satoru Iwata , S. Thomas Mccormick, Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow, Mathematics of Operations Research, v.25 n.1, p.76-104, February 2000 [doi>10.1287/moor.25.1.76.15208]
	19	A. S. Schulz and R. Weismantel, "A polynomial-time augmentation algorithm for integer programming," Manuscript, F~chbereit Mathmatik, Technische Universit~it Berlin (1998).
	20	Eva Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research, v.34 n.2, p.250-256, March-April 1986 [doi>10.1287/opre.34.2.250]
	21	C. Wallacher, "A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms," unpublished manuscript, institute ffir Angewandte Mathematik, Technische Universit~it Braunschweig (1989).
	22	Kevin D. Wayne, A polynomial combinatorial algorithm for generalized minimum cost flow, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.11-18, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301261]
	23	A. Weintraub, "A primal algorithm to solve network flow problems with convex costs," Management Sci. 21, 87-97 (1974).
	24	N. Zadeh, "More pathological examples for network flow problems,~' Math. Programming 5, 217-224 (1973).