A short proof for stronger version of DS decomposition in set function optimization (Q830927)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A short proof for stronger version of DS decomposition in set function optimization |
scientific article; zbMATH DE number 7346743
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A short proof for stronger version of DS decomposition in set function optimization |
scientific article; zbMATH DE number 7346743 |
Statements
A short proof for stronger version of DS decomposition in set function optimization (English)
0 references
10 May 2021
0 references
This brief article presents an alternative, short proof of the claim that every set function can be decomposed into the difference of two monotone increasing, strictly submodular functions. This article begin with the study of two similar theorems in DS decomposition. The shortened version of the proof provides a constructive algorithm which may, in the future, result in improved optimization algorithms.
0 references
set function
0 references
DS decomposition
0 references
monotone nondecreasing
0 references
submodular
0 references
supermodular
0 references
0 references
