Minimizing a sum of submodular functions

V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258.


Journal Article | Published | English
Department
Abstract
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.
Publishing Year
Date Published
2012-10-01
Journal Title
Discrete Applied Mathematics
Volume
160
Issue
15
Page
2246 - 2258
IST-REx-ID

Cite this

Kolmogorov V. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 2012;160(15):2246-2258. doi:10.1016/j.dam.2012.05.025
Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete Applied Mathematics, 160(15), 2246–2258. https://doi.org/10.1016/j.dam.2012.05.025
Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete Applied Mathematics 160, no. 15 (2012): 2246–58. https://doi.org/10.1016/j.dam.2012.05.025.
V. Kolmogorov, “Minimizing a sum of submodular functions,” Discrete Applied Mathematics, vol. 160, no. 15, pp. 2246–2258, 2012.
Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 160(15), 2246–2258.
Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete Applied Mathematics, vol. 160, no. 15, Elsevier, 2012, pp. 2246–58, doi:10.1016/j.dam.2012.05.025.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar