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: William H Cunningham, On submodular function minimization, Combinatorica, v.5 n.3, p.185-192, 1985 [doi>10.1007/BF02579361]
• 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: 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]
• 9: Thomas R. Ervolina , S. Thomas McCormick, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Discrete Applied Mathematics, v.46 n.2, p.133-165, Oct. 12, 1993 [doi>10.1016/0166-218X(93)90025-J]
• 10: Lisa Fleischer , Satoru Iwata, Improved algorithms for submodular function minimization and submodular flow, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.107-116, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335318]
• 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: 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]
• 14: 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]
• 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: Bruce Hoppe , Òva Tardos, The Quickest Transshipment Problem, Mathematics of Operations Research, v.25 n.1, p.36-62, February 2000 [doi>10.1287/moor.25.1.36.15211]
• 27: 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]
• 28: 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]
• 29: 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]
• 30: 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
• 31: 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]
• 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: 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]
• 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: 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]
• 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: 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]
• 40: Éva Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, v.5 n.3, p.247-255, 1985 [doi>10.1007/BF02579369]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms

Keywords:
Discrete optimization, strongly polynomial algorithm, submodular function