A fully combinatorial algorithm for submodular function minimization

ABSTRACT

This paper presents a strongly polynomial algorithm for submodular function minimization using only additions, subtractions, comparisons, and oracle calls for function values.

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¨onheim, eds., Gordon and Breach, 69-87, 1970.
• 4: L. Fleischer, S. Iwata, and S. T. McCormick: A faster capacity scaling algorithm for submodular flow, Math. Programming, to appear.
• 5: 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]
• 6: S Fujishige, A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm, Mathematical Programming: Series A and B, v.35 n.3, p.298-308, July 1986 [doi>10.1007/BF01580882]
• 7: S. Fujishige: Submodular Functions and Optimization, North-Holland, 1991.
• 8: S. Fujishige and N. Tomizawa: A note on submodular functions on distributive lattices, J. Oper. Res. Soc. Japan, 26 (1983), 309-318.
• 9: M. Grötschel, L. Lovász, and A. Schrijver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 169-197.
• 10: M. Grótschel, L. Lovász, and A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.
• 11: 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]
• 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: 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]
• 15: M. Queyranne: Minimizing symmetric submodular functions, Math. Programming, 82 (1998), 3-12.
• 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]
• 17: L. S. Shapley: Cores of convex games, Int. J. Game Theory, 1 (1971), 11-26.
• 18: Éva Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, v.5 n.3, p.247-255, 1985 [doi>10.1007/BF02579369]