Name
Abstract | ||
|---|---|---|
AbstractA k-submodular function is a generalization of submodular and bisubmodular functions. This paper establishes a compact representation for minimizers of a k-submodular function by a poset with inconsistent pairs (PIP). This is a generalization of Ando---Fujishige's signed poset representation for minimizers of a bisubmodular function. We completely characterize the class of PIPs (elementary PIPs) arising from k-submodular functions. We give algorithms to construct the elementary PIP of minimizers of a k-submodular function f for three cases: (i) a minimizing oracle of f is available, (ii) f is network-representable, and (iii) f arises from a Potts energy function. Furthermore, we provide an efficient enumeration algorithm for all maximal minimizers of a Potts k-submodular function. Our results are applicable to obtain all maximal persistent labelings in actual computer vision problems. We present experimental results for real vision instances. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10878-017-0142-0 | Periodicals |
Keywords | Field | DocType |
k-submodular function,Birkhoff representation theorem,Poset with inconsistent pairs (PIP),Potts energy function | Discrete mathematics,Combinatorics,Mathematical optimization,Submodular set function,Oracle,Enumeration algorithm,Mathematics,Partially ordered set | Journal |
Volume | Issue | ISSN |
36 | 3 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiroshi Hirai | 1 | 8 | 2.99 |
| Taihei Oki | 2 | 0 | 1.69 |