A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions

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. E. Bixby, W. H. Cunningham, and D. M. Topkis: Partial order of a polymatroid extreme point, Math. Oper. Res., 10 (1985), 367-378.
	2	W. H. Cunningham: Testing membership in matroid polyhedra, J. Combinatorial Theory, B36 (1984), 161-188.
	3	William H Cunningham, On submodular function minimization, Combinatorica, v.5 n.3, p.185-192, 1985 [doi>10.1007/BF02579361]
	4	J. Edmonds: Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Sch6nheim, eds., Gordon and Breach, 69- 87, 1970.
	5	J. Edmonds and R. Giles: A min-max relation for submodular function on graphs, Ann. Discrete Math., I (1977), 185-204.
	6	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]
	7	L. Fleischer, S. Iwata, and S. T. McCormick: A faster capacity scaling algorithm for submodular flow, 1999.
	8	A. Frank: An algorithm for submodular functions on graphs, Ann. Discrete Math., 16 (1982), 189- 212.
	9	A. Frank , Éva Tardos, An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, v.7 n.1, p.49-65, Jan. 1987 [doi>10.1007/BF02579200]
	10	A. Frank , É. Tardoes, Generalized polymatroids and submodular flows, Mathematical Programming: Series A and B, v.42 n.3, p.489-563, Dec. 1988 [doi>10.1007/BF01589418]
	11	S. Fujishige: Polymatroidal dependence structure of a set of random variables, Information and Control, 39 (1978), 55-72.
	12	S. Fujishige: Lexicographically optimal base of a polymatroid with respect to a weight vector, Math. Oper. Res., 5 (1980), 186-196.
	13	S. Fujishige: Submodular systems and related topics, Math. Programming Study, 22 (1984), 113-131.
	14	S. Fujishige: Theory of submodular programs: A Fenchel-type rain-max theorem and subgradients of submodular functions, Math. Programming, 29 (1984), 142-155.
	15	S. Fujishige: $ubmodular Functions and Optimization, North-Holland, 1991.
	16	M. X. Goemans and V. S. Ramakrishnan: Minimizing submodular functions over familiesof subsets, Combinatorica, 15 (1995), 499-513.
	17	M. Gr5tschel, L. Lovg~sz, and A. Schrijver' The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, I (1981), 169- 197.
	18	M. Gr5tschel, L. Lov~sz, and A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.
	19	T.-S. Hart: The capacity region of general multipleaccess channel with correlated sources, Information and Control, 40 (1979), 37-60.
	20	Bruce Hoppe , Éva Tardos, “The quickest transshipment problem”, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.512-521, January 22-24, 1995, San Francisco, California, United States
	21	Hisashi Ito , Satoru Iwata , Kazuo Murota, Block-Triangularizations of Partitioned Matrices under Similarity/Equivalence Transformations, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1226-1255, Oct. 1994 [doi>10.1137/S0895479892235599]
	22	Satoru Iwata, A capacity scaling algorithm for convex cost submodular flows, Mathematical Programming: Series A and B, v.76 n.2, p.299-308, Feb. 1, 1997 [doi>10.1007/BF02614442]
	23	Satoru Iwata , S. Thomas McCormick , Maiko Shigeno, A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.259-272, June 09-11, 1999
	24	Satoru Iwata , Kazuo Murota, A Minimax Theorem and a Dulmage--Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices, SIAM Journal on Matrix Analysis and Applications, v.16 n.3, p.719-734, July 1995 [doi>10.1137/S0895479893255901]
	25	L. Lovg~sz: Submodular functions and convexity. Mathematical Programming -- The State o/ the Art, A. Bachem, M. Gr5tschel and B. Korte, eds., Springer-Verlag, 1983, 235-257.
	26	Hiroshi Nagamochi , Toshihide Ibaraki, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, v.5 n.1, p.54-66, Feb. 1992 [doi>10.1137/0405004]
	27	H. Narayanan: A rounding technique for the polymatroid membership problem, Linear Algebra Appl., 221 (1995), 41-57.
	28	M. Queyranne: Minimizing symmetric submodular functions, Math. Programming, 82 (1998), 3-12.
	29	Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]
	30	M. A. Sohoni: Membership in submodular and other polyhedra. Technical Report TR-102-92, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, India, 1992.
	31	Arie Tamir, A unifying location model on tree graphs based on submodularity properties, Discrete Applied Mathematics, v.47 n.3, p.275-283, Dec. 21, 1993 [doi>10.1016/0166-218X(93)90132-8]
	32	Éva Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, v.5 n.3, p.247-255, 1985 [doi>10.1007/BF02579369]