---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Kolmogorov, Vladimir
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1016/j.dam.2012.05.025
bibo_issue: '15'
bibo_volume: 160
dct_date: 2012^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: Minimizing a sum of submodular functions@
...