Improved algorithms for submodular function minimization and submodular flow

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved algorithms for submodular function minimization and submodular flow

Full text

Pdf (1.06 MB)

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: 107 - 116

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Lisa Fleischer	Dept. of Ind. Eng. & Oper. Res., Columbia University, New York, NY
Satoru Iwata	Grad. School of Eng. Science, Osaka University, Toyonaka, Osaka 560-8531, Japan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 39, Citation Count: 3

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/335305.335318 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	W. H. Cunningham. Testing membership in matroid polyhedra. J. Combinatorial Theory B, 36:161-188, 1984.
	2	William H Cunningham, On submodular function minimization, Combinatorica, v.5 n.3, p.185-192, 1985 [doi>10.1007/BF02579361]
	3	J. Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Sch/Snheim, editors, Combinatorial Structures and their Applications, pages 69-87. Gordon and Breach, 1970.
	4	J. Edmonds and R. Giles. A min-max relation for submodular functions on graphs. Ann. Discrete Math., 1:185-204, 1977.
	5	L. Fleischer, S, Iwata, and S. T. McCormick. A faster capacity scaling algorithm for submodular flow. Technical Report 9947, C.O.R.E. Discussion Paper, Louvain-la-Neuve, Belgium, 1999.
	6	A. Frank. Finding feasible vectors of Edmonds-Giles polyhedra. J. Combin. Theory, 36:221-239, 1984.
	7	A. Frank and l~. Tardos. An application of submodular flows. Linear algebra and its applications, 114/115:329--348, 1989.
	8	S. Fujishige , H. Röck , U. Zimmermann, A strongly polynomial algorithm for minimum cost submodular flow problems, Mathematics of Operations Research, v.14 n.1, p.60-69, Feb. 1989 [doi>10.1287/moor.14.1.60]
	9	S. Fujishige and X. Zhang. New algorithms for the intersection problem of submodular systems. Japan J. lndust. Appl. Math., 9:369-382, 1992.
	10	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]
	11	M. Grotschel, L. Lovasz, and A, Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981.
	12	Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.97-106, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335317]
	13	S. Iwata, S. T. McCormick, and M. Shigeno. A fast cost scaling algorithm for submodular flow. To appear.
	14	Tibor Jordán, Edge-Splitting Problems with Demands, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.273-288, June 09-11, 1999
	15	M. Queyranne. Minimizing symmetric submodular functions. Math. Programming, 82:3-12, 1998.
	16	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]

CITED BY 3

	Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001
	Jens Vygen, A note on Schrijver's submodular function minimization algorithm, Journal of Combinatorial Theory Series B, v.88 n.2, p.399-402, July 2003
	David A. Cohen , Martin C. Cooper , Peter G. Jeavons , Andrei A. Krokhin, The complexity of soft constraint satisfaction, Artificial Intelligence, v.170 n.11, p.983-1016, August 2006