Minimizing a sum of submodular functions
Kolmogorov, Vladimir
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.
Elsevier
2012
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/3117
Kolmogorov V. Minimizing a sum of submodular functions. <i>Discrete Applied Mathematics</i>. 2012;160(15):2246-2258. doi:<a href="https://doi.org/10.1016/j.dam.2012.05.025">10.1016/j.dam.2012.05.025</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2012.05.025
info:eu-repo/semantics/openAccess