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.
- BIXBY, R. E., CUNNINGHAM,W.H.,AND TOPKIS, D. M. 1985. Partial order of a polymatroid extreme point. Math. Oper. Res. 10, 367-378.]]Google ScholarDigital Library
- CUNNINGHAM, W. H. 1984. Testing membership in matroid polyhedra. J. Combinat. Theory B36, 161- 188.]]Google ScholarCross Ref
- CUNNINGHAM, W. H. 1985. On submodular function minimization. Combinatorica 5, 185-192.]] Google ScholarDigital Library
- CUNNINGHAM,W.H.,AND FRANK, A. 1985. A primal-dual algorithm for submodular flows. Math. Oper. Res. 10, 251-262.]]Google ScholarDigital Library
- EDMONDS, J. 1967. Systems of distinct representatives and linear algebra. J. Res. NBS 71B, 241-245.]]Google Scholar
- 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.]]Google Scholar
- EDMONDS, J., AND GILES, R. 1977. Amin-max relation for submodular functions on graphs. Ann. Discrete Math. 1, 185-204.]]Google ScholarCross Ref
- EDMONDS, J., AND KARP, R. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 2 (Apr.), 248-264.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- FLEISCHER, L., IWATA, S., AND MCCORMICK, S. T. 2001. A faster capacity scaling algorithm for submodular flow. Math. Prog., to appear.]]Google Scholar
- FRANK, A. 1982. An algorithm for submodular functions on graphs. Ann. Discrete Math. 16, 189-212.]]Google Scholar
- FRANK, A., AND TARDOS, E. 1987. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49-65.]] Google ScholarDigital Library
- FRANK, A., AND TARDOS, E. 1988. Generalized polymatroids and submodular flows. Math. Prog. 42, 489-563.]] Google ScholarDigital Library
- FRANK, A., AND TARDOS, E. 1989. An application of submodular flows. Linear Alg. Appl. 114/115, 329-348.]]Google ScholarCross Ref
- FUJISHIGE, S. 1978. Polymatroidal dependence structure of a set of random variables. Inf. Contr. 39, 55-72.]]Google ScholarCross Ref
- FUJISHIGE, S. 1980. Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5, 186-196.]]Google ScholarDigital Library
- FUJISHIGE, S. 1984a. Submodular systems and related topics. Math. Prog. Study 22, 113-131.]]Google ScholarCross Ref
- FUJISHIGE, S. 1984b. Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions. Math. Prog. 29, 142-155.]]Google ScholarDigital Library
- FUJISHIGE, S. 1991. Submodular Functions and Optimization. North-Holland, Amsterdam, The Netherlands.]]Google Scholar
- FUJISHIGE, S., AND IWATA, S. 2000. Algorithms for submodular flows. IEICE Trans. Inform. Syst. E83-D, 322-329.]]Google Scholar
- GOEMANS,M.X.,AND RAMAKRISHNAN, V. S. 1995. Minimizing submodular functions over families of subsets. Combinatorica 15, 499-513.]]Google ScholarCross Ref
- GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169-197.]]Google ScholarCross Ref
- GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.]]Google Scholar
- HAN, T.-S. 1979. The capacity region of general multiple-access channel with correlated sources. Inf. Cont. 40, 37-60.]]Google ScholarCross Ref
- HOPPE, B., AND TARDOS, E. 2000. The quickest transshipment problem. Math. Oper. Res. 25, 36-62.]]Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- IWATA, S. 1997. A capacity scaling algorithm for convex cost submodular flows. Math. Prog. 76, 299- 308.]]Google ScholarDigital Library
- IWATA, S. 2001. A fully combinatorial algorithm for submodular function minimization. J. Combinat. Theory, in press.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]]Google Scholar
- NAGAMOCHI, H., AND IBARAKI, T. 1992. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Disc. Math. 5, 54-64.]] Google ScholarDigital Library
- NARAYANAN, H. 1995. A rounding technique for the polymatroid membership problem. Linear Alg. Appl. 221, 41-57.]]Google ScholarCross Ref
- QUEYRANNE, M. 1998. Minimizing symmetric submodular functions. Math. Prog. 82, 3-12.]]Google ScholarCross Ref
- SCHRIJVER, A. 2000. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combinat. Theory B80, 346-355.]] Google ScholarDigital Library
- SHAPLEY, L. S. 1971. Cores of convex games. Int. J. Game Theory 1, 11-26.]]Google ScholarDigital Library
- 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.]]Google Scholar
- TAMIR, A. 1993. A unifying location model on tree graphs based on submodularity properties. Disc. Appl. Math. 47, 275-283.]] Google ScholarDigital Library
- TARDOS, E. 1985. A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 247- 255.]] Google ScholarDigital Library
Index Terms
- A combinatorial strongly polynomial algorithm for minimizing submodular functions
Recommendations
K-submodular functions and convexity of their Lovász extension
We consider a class of lattice polyhedra introduced by Hoffman and Schwartz. The polyhedra are defined in terms of a kind of submodular function defined on the set of antichains of a poset. Recently, Krüger (Discrete Appl. Math. 99 (2000) 125-148) ...
A strongly polynomial algorithm for line search in submodular polyhedra
A submodular polyhedron is a polyhedron associated with a submodular function. This paper presents a strongly polynomial time algorithm for line search in submodular polyhedra with the aid of a fully combinatorial algorithm for submodular function ...
Quadratic M-convex and L-convex functions
The concepts of L-convexity and M-convexity are introduced by Murota (1996) for functions defined over the integer lattice, and recently extended to polyhedral convex functions by Murota-Shioura (2000). L-convex and M-convex functions are deeply ...
Comments