A compact representation for minimizers of \(k\)-submodular functions (Q1631630)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A compact representation for minimizers of \(k\)-submodular functions |
scientific article |
Statements
A compact representation for minimizers of \(k\)-submodular functions (English)
0 references
6 December 2018
0 references
The authors establish a compact representation for minimizers of a \(k\) submodular function. This can be viewed as a generalization of the poset representation for submodular functions and Ando-Fujishige's signed poset representation for bisubmodular functions. Minimizers of a \(k\)-submodular function form a median semilattice and, by a Birkhoff-type representation theorem for median semilattices, the minimizer set is represented by a poset with inconsistent pairs (PIP), where minimizers are encoded into special ideals in the PIP, called consistent ideals. PIPs arising from \(k\)-submodular functions are rather special, The authors completely characterize such PIPs and this representation is actually compact. The authors further show that the size of the elementary PIP for a \(k\)-submodular function of \(n\) variables is \(\mathcal{O}(kn)\) and present algorithms to construct the elementary PIP of the minimizers of a \(k\) submodular function \(f\) under the situations: (i) A minimizing oracle of \( f \) is given. (ii) \(f\) is network-representable. (iii) \(f\) arises from a Potts energy function. Furthermore, the authors provide an efficient enumeration algorithm for all maximal minimizers of a Potts \(k\)-submodular function. For a Potts \(k\)-submodular function, the problem of enumerating all maximal minimizers reduces to the problem of enumerating all ideals of a single poset. Experimental results are also presented for real instances.
0 references
\(k\)-submodular function
0 references
Birkhoff representation theorem
0 references
poset with inconsistent pairs (PIP)
0 references
Potts energy function
0 references
0 references
0 references