Minimizing a sum of submodular functions. (English) Zbl 1274.90461
Summary: We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms.
A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines.
We then explore in more detail Iwata’s capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms.
A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines.
We then explore in more detail Iwata’s capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms.
MSC:
| 90C35 | Programming involving graphs or networks |
Keywords:
submodular minimizationSoftware:
MAXFLOWReferences:
| [1] | Aggarwal, A.; Klawe, M. M.; Moran, S.; Shor, P.; Wilber, R., Geometric applications of a matrix-searching algorithm, Algorithmica, 2, 195-208 (1987) · Zbl 0642.68078 |
| [2] | Billionnet, A.; Minoux, M., Maximizing a supermodular pseudo-Boolean function: a polynomial algorithm for supermodular cubic functions, Discrete Applied Mathematics, 12, 1, 1-11 (1985) · Zbl 0583.90067 |
| [3] | Boykov, Y.; Kolmogorov, V., An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 11, 1124-1137 (2004) |
| [4] | Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rdiger, Perspectives of monge properties in optimization, Discrete Applied Mathematics, 70, 2, 95-161 (1996) · Zbl 0856.90091 |
| [5] | Cooper, Martin C., Minimization of locally defined submodular functions by optimal soft arc consistency, Constraints, 13, 4, 437-458 (2008) · Zbl 1180.90262 |
| [6] | Delong, Andrew; Osokin, Anton; Isack, Hossam; Boykov, Yuri, Fast approximate energy minimization with label costs, Computer Vision and Pattern Recognition, 2173-2180 (2010) · Zbl 1235.68257 |
| [7] | Edmonds, J., Submodular functions, matroids, and certain polyhedra, (Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J., Combinatorial Structures and their Applications, vol. 17 (1970), Gordon and Breach), 69-87 · Zbl 0268.05019 |
| [8] | Edmonds, Jack; Giles, Rick, A min-max relation for submodular functions on graphs, Annals of Discrete Mathematics, 1, 185-204 (1977) · Zbl 0373.05040 |
| [9] | Fleischer, L.; Iwata, S.; McCormick, S. T., A faster capacity scaling algorithm for submodular flow, Mathematical Programming, 92, 119-139 (2002) · Zbl 1046.90073 |
| [10] | Freedman, D.; Drineas, P., Energy minimization via graph cuts: settling what is possible, Computer Vision and Pattern Recognition, 939-946 (2005) |
| [11] | Fujishige, Satoru, Algorithms for solving the independent-flow problems, Journal of the Operations Research Society of Japan, 21, 189-204 (1978) · Zbl 0388.05007 |
| [12] | Fujishige, S., Submodular Functions and Optimization (1991), North-Holland · Zbl 0728.90056 |
| [13] | Fujishige, S.; Iwata, S., Minimizing a submodular function arising from a concave function, Discrete Applied Mathematics, 92, 2-3, 211-215 (1999) · Zbl 0973.90059 |
| [14] | Fujishige, Satoru; Iwata, Satoru, Algorithms for submodular flows, IEICE Transactions on Information and Systems, E83-D, 3, 322-329 (2000) · Zbl 1296.90104 |
| [15] | Fujishige, S.; Zhang, X., New algorithms for the intersection problem of submodular systems, Japan Journal of Industrial and Applied Mathematics, 9, 369-382 (1992) · Zbl 0770.90073 |
| [16] | Goldberg, Andrew V.; Rao, Satish, Beyond the flow decomposition barrier, Journal of the ACM, 45, 5, 783-797 (1998) · Zbl 1064.90567 |
| [17] | Dorit S. Hochbaum, Vikas Singh, An efficient algorithm for co-segmentation, in: ICCV, 2009, pp. 269-276.; Dorit S. Hochbaum, Vikas Singh, An efficient algorithm for co-segmentation, in: ICCV, 2009, pp. 269-276. |
| [18] | Iwata, S., A faster scaling algorithm for minimizing submodular functions, SIAM Journal on Computing, 32, 4, 833-840 (2003) · Zbl 1033.90106 |
| [19] | Iwata, S., A capacity scaling algorithm for convex cost submodular flows, Mathematical Programming, 76, 2, 299-308 (1997) · Zbl 0882.90037 |
| [20] | Satoru Iwata, James B. Orlin, A simple combinatorial algorithm for submodular function minimization, SODA. 2009, pp. 1230-1237.; Satoru Iwata, James B. Orlin, A simple combinatorial algorithm for submodular function minimization, SODA. 2009, pp. 1230-1237. · Zbl 1423.90226 |
| [21] | Iwata, Satoru; Thomas McCormick, S.; Shigeno, Maiko, A fast cost scaling algorithm for submodular flow, Information Processing Letters, 74, 3-4, 123-128 (2000) · Zbl 1339.90325 |
| [22] | Kohli, P.; Ladicky, L.; Torr, P., Robust higher order potentials for enforcing label consistency, International Journal of Computer Vision, 82, 3, 302-324 (2009) |
| [23] | Kohli, Pushmeet; Pawan Kumar, M.; Torr, Philip H. S., \(P^3\) & beyond: move making algorithms for solving higher order functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, 31, 9, 1645-1656 (2009) |
| [24] | Vladimir Kolmogorov, Minimizing a sum of submodular functions, Tech. Rep., June 2010. arXiv:1006.1990v1; Vladimir Kolmogorov, Minimizing a sum of submodular functions, Tech. Rep., June 2010. arXiv:1006.1990v1 · Zbl 1274.90461 |
| [25] | Orlin, James B., A faster strongly polynomial time algorithm for submodular function minimization, Mathematical Programming, 118, 2, 237-251 (2009) · Zbl 1179.90290 |
| [26] | Queyranne, Maurice, Minimizing symmetric submodular functions, Mathematical Programming, 82, 1-2, 3-12 (1998) · Zbl 0949.90076 |
| [27] | Peter Stobbe, Andreas Krause, Efficient minimization of decomposable submodular functions, in: Proc. Neural Information Processing Systems, NIPS, 2010, pp. 2208-2216.; Peter Stobbe, Andreas Krause, Efficient minimization of decomposable submodular functions, in: Proc. Neural Information Processing Systems, NIPS, 2010, pp. 2208-2216. |
| [28] | Sara Vicente, Vladimir Kolmogorov, Carsten Rother, Joint optimization of segmentation and appearance models, ICCV, 2009, pp. 755-762.; Sara Vicente, Vladimir Kolmogorov, Carsten Rother, Joint optimization of segmentation and appearance models, ICCV, 2009, pp. 755-762. |
| [29] | Živný, Stanislav; Cohen, David A.; Jeavons, Peter G., The expressive power of binary submodular functions, Discrete Applied Mathematics, 157, 15, 3347-3358 (2009) · Zbl 1229.90093 |
| [30] | Živný, Stanislav; Jeavons, Peter G., Classes of submodular constraints expressible by graph cuts, Constraints, 15, 3, 430-445 (2010) · Zbl 1208.68196 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
