19.03.2020 | Ausgabe 1/2020
A variation of DS decomposition in set function optimization
- Zeitschrift:
- Journal of Combinatorial Optimization > Ausgabe 1/2020
Wichtige Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Abstract
Any set function can be decomposed into the difference of two monotone nondecreasing submodular functions. This theorem plays an important role in the set function optimization theory. In this paper, we show a variation that any set function can be decomposed into the difference of two monotone nondecreasing supermodular functions. Meanwhile, we give an example in social network optimization and construct algorithmic solutions for the maximization problem of set functions with this variation of DS decomposition.
