A short proof for stronger version of DS decomposition in set function optimization
type: Item
instance of: scholarly article
title: A short proof for stronger version of DS decomposition in set function optimization
author: Xiang Li
author: H. George Du
published in: Journal of Combinatorial Optimization
publication date: 2021-05-10T00:00:00Z
review text: 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.
reviewed by: Efstratios Rappos
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 7346743
zbMATH Keywords: set function
zbMATH Keywords: DS decomposition
zbMATH Keywords: monotone nondecreasing
zbMATH Keywords: submodular
zbMATH Keywords: supermodular
MaRDI profile type: Publication
full work available at URL: s10878-020-00639-4
OpenAlex ID: W3071724945
cites work: Design and analysis of approximation algorithms
cites work: A fast double greedy algorithm for non-monotone DR-submodular function maximization
cites work: Monotone submodular maximization over the bounded integer lattice with cardinality constraints
cites work: A variation of DS decomposition in set function optimization
cites work: Set function optimization
DOI: 10.1007/S10878-020-00639-4
description: scientific article; zbMATH DE number 7346743