A simple combinatorial algorithm for submodular function minimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A simple combinatorial algorithm for submodular function minimization

Full text

Pdf (463 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 1230-1237

Year of Publication: 2009

Authors

Satoru Iwata	Kyoto University, Kyoto, Japan
James B. Orlin	MIT, Cambridge, MA

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 124, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

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

ABSTRACT

This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n⁶EO log nM) time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O ((n⁴EO+n⁵)log nM) time. The strongly polynomial version of this faster algorithm runs in O((n⁵EO + n⁶) log n) time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization. The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.

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. Combin. Theory, B36 (1984), 161--188.
	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, Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, 69--87, 1970.
	4	Lisa Fleischer , Satoru Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics, v.131 n.2, p.311-322, 12 September 2003 [doi>10.1016/S0166-218X(02)00458-4]
	5	S. Fujishige: Submodular Functions and Optimization, Elsevier, 2005.
	6	M. X. Goemans and V. S. Ramakrishnan: Minimizing submodular functions over families of sets, Combinatorica, 15 (1995), 499--513.
	7	M. Grötschel, L. Lovász, and A. Schrijver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 169--197.
	8	M. Grötschel, L. Lovász, and A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.
	9	Satoru Iwata, A fully combinatorial algorithm for submodular function minimization, Journal of Combinatorial Theory Series B, v.84 n.2, p.203-212, March 2002 [doi>10.1006/jctb.2001.2072]
	10	S. Iwata: A faster scaling algorithm for minimizing submodular functions, SIAM J. Comput., 32 (2003), 833--840.
	11	Satoru Iwata, Submodular function minimization, Mathematical Programming: Series A and B, v.112 n.1, p.45-64, July 2007 [doi>10.1007/s10107-006-0084-2]
	12	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 [doi>10.1145/502090.502096]
	13	L. Lovász: Submodular functions and convexity. Mathematical Programming --- The State of the Art, A. Bachem, M. Grötschel and B. Korte, eds., Springer-Verlag, 1983, 235--257.
	14	S. T. McCormick: Submodular function minimization, Discrete Optimization (K. Aardal, G. Nemhauser, R. Weismantel, eds., Handbooks in Operations Research, 12, Elsevier, 2005), 321--391.
	15	K. Nagano: A strongly polynomial algorithm for line search in submodular polyhedra, Discrete Optim., 4 (2007), 349--359.
	16	James B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization, Mathematical Programming: Series A and B, v.118 n.2, p.237-251, January 2009 [doi>10.1007/s10107-007-0189-2]
	17	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]
	18	L. S. Shapley: Cores of convex games, Int. J. Game Theory, 1 (1971), 11--26.