A combinatorial strongly polynomial algorithm for minimizing submodular functions

Abstract

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, and Schrijver. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the length of the largest absolute function value. The paper also presents a strongly polynomial version in which the number of steps is bounded by a polynomial in the size of the underlying set, independent of the function values.

References

1. BIXBY, R. E., CUNNINGHAM,W.H.,AND TOPKIS, D. M. 1985. Partial order of a polymatroid extreme point. Math. Oper. Res. 10, 367-378.]]
2. CUNNINGHAM, W. H. 1984. Testing membership in matroid polyhedra. J. Combinat. Theory B36, 161- 188.]]
3. CUNNINGHAM, W. H. 1985. On submodular function minimization. Combinatorica 5, 185-192.]]
4. CUNNINGHAM,W.H.,AND FRANK, A. 1985. A primal-dual algorithm for submodular flows. Math. Oper. Res. 10, 251-262.]]
5. EDMONDS, J. 1967. Systems of distinct representatives and linear algebra. J. Res. NBS 71B, 241-245.]]
6. EDMONDS, J. 1970. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications. R. Guy, H. Hanani, N. Sauer, and J. Schonheim, Eds. Gordon and Breach, pp. 69-87.]]
7. EDMONDS, J., AND GILES, R. 1977. Amin-max relation for submodular functions on graphs. Ann. Discrete Math. 1, 185-204.]]
8. EDMONDS, J., AND KARP, R. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 2 (Apr.), 248-264.]]
9. ERVOLINA,T.R.,AND MCCORMICK, S. T. 1993. Two strongly polynomial cut canceling algorithms for minimum cost network flow. Disc. Appl. Math. 46, 13-165.]]
10. FLEISCHER, L., AND IWATA, S. 2000. Improved algorithms for submodular function minimization and submodular flow. In Proceedings of the 32nd Annual ACMSymposium on Theory of Computing (Portland, Ore., May 21-23). ACM, New York, pp. 107-116.]]
11. FLEISCHER, L., IWATA, S., AND MCCORMICK, S. T. 2001. A faster capacity scaling algorithm for submodular flow. Math. Prog., to appear.]]
12. FRANK, A. 1982. An algorithm for submodular functions on graphs. Ann. Discrete Math. 16, 189-212.]]
13. FRANK, A., AND TARDOS, E. 1987. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49-65.]]
14. FRANK, A., AND TARDOS, E. 1988. Generalized polymatroids and submodular flows. Math. Prog. 42, 489-563.]]
15. FRANK, A., AND TARDOS, E. 1989. An application of submodular flows. Linear Alg. Appl. 114/115, 329-348.]]
16. FUJISHIGE, S. 1978. Polymatroidal dependence structure of a set of random variables. Inf. Contr. 39, 55-72.]]
17. FUJISHIGE, S. 1980. Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5, 186-196.]]
18. FUJISHIGE, S. 1984a. Submodular systems and related topics. Math. Prog. Study 22, 113-131.]]
19. FUJISHIGE, S. 1984b. Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions. Math. Prog. 29, 142-155.]]
20. FUJISHIGE, S. 1991. Submodular Functions and Optimization. North-Holland, Amsterdam, The Netherlands.]]
21. FUJISHIGE, S., AND IWATA, S. 2000. Algorithms for submodular flows. IEICE Trans. Inform. Syst. E83-D, 322-329.]]
22. GOEMANS,M.X.,AND RAMAKRISHNAN, V. S. 1995. Minimizing submodular functions over families of subsets. Combinatorica 15, 499-513.]]
23. GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169-197.]]
24. GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.]]
25. HAN, T.-S. 1979. The capacity region of general multiple-access channel with correlated sources. Inf. Cont. 40, 37-60.]]
26. HOPPE, B., AND TARDOS, E. 2000. The quickest transshipment problem. Math. Oper. Res. 25, 36-62.]]
27. ITO, H., IWATA, S., AND MUROTA, K. 1994. Block-triangularization of partitioned matrices under similarity/ equivalence transformations. SIAM J. Matrix Anal. Appl. 15, 1226-1255.]]
28. IWATA, S. 1997. A capacity scaling algorithm for convex cost submodular flows. Math. Prog. 76, 299- 308.]]
29. IWATA, S. 2001. A fully combinatorial algorithm for submodular function minimization. J. Combinat. Theory, in press.]]
30. IWATA, S., MCCORMICK,S.T.,AND SHIGENO, M. 1999. A strongly polynomial cut canceling algorithm for the submodular flow problem. In Proceedings of the 7th MPS Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag, Berlin, Germany, pp. 259-272.]]
31. IWATA, S., AND MUROTA, K. 1995. Aminimax theorem and a Dulmage-Mendelsohn type decomposition for a class of generic partitioned matrices. SIAM J. Matrix Anal. Appl. 16, 719-734.]]
32. LOVASZ, L. 1983. Submodular functions and convexity. In Mathematical Programming-The State of the Art, A. Bachem, M. Grotschel and B. Korte, Eds. Springer-Verlag, New York, pp. 235-257.]]
33. NAGAMOCHI, H., AND IBARAKI, T. 1992. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Disc. Math. 5, 54-64.]]
34. NARAYANAN, H. 1995. A rounding technique for the polymatroid membership problem. Linear Alg. Appl. 221, 41-57.]]
35. QUEYRANNE, M. 1998. Minimizing symmetric submodular functions. Math. Prog. 82, 3-12.]]
36. SCHRIJVER, A. 2000. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combinat. Theory B80, 346-355.]]
37. SHAPLEY, L. S. 1971. Cores of convex games. Int. J. Game Theory 1, 11-26.]]
38. SOHONI, M. A. 1992. Membership in submodular and other polyhedra. Tech. Rep. TR-102-92. Dept. Comput. Sci. Eng., Indian Institute of Technology, Bombay, India.]]
39. TAMIR, A. 1993. A unifying location model on tree graphs based on submodularity properties. Disc. Appl. Math. 47, 275-283.]]
40. TARDOS, E. 1985. A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 247- 255.]]

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

• Theory of computation

  • Randomness, geometry and discrete structures