Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
type: Item
instance of: scholarly article
title: Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
zbMATH Open document ID: 1479.90182
author: Zhenning Zhang
author: Yanjun Jiang
author: Donglei Du
author: Chenchen Wu
published in: Journal of Global Optimization
publication date: 2021-08-17T00:00:00Z
review text: The authors propose a threshold greedy algorithm for the problem of maximizing the sum of a monotone non-negative diminishing return submodular function and a monotone non-negative supermodular function on the integer lattice with a cardinality constraint. The relation between the value of the solution returned by the proposed algorithm and the optimal solution value is estimated by a constant. With this purpose the authors introduce a concept of the total curvature on the integer lattice for a monotone non-decreasing non-negative submodular function and for a monotone non-negative supermodular function. They also formulate a linear program whose objective function approximates the estimated relation.
reviewed by: Svetlana A. Kravchenko
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 7382627
zbMATH Keywords: submodular function
zbMATH Keywords: supermodular function
zbMATH Keywords: integer lattice
zbMATH Keywords: cardinality constraint
zbMATH Keywords: threshold greedy algorithm
MaRDI profile type: Publication
full work available at URL: s10898-021-01014-1
OpenAlex ID: W3142764332
cites work: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
cites work: Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
cites work: Maximization of submodular functions: theory and enumeration algorithms
cites work: Q2941641
cites work: Q3096108
cites work: Best Algorithms for Approximating the Maximum of a Submodular Set Function
cites work: An analysis of approximations for maximizing submodular set functions—I
cites work: Maximizing monotone submodular functions over the integer lattice
cites work: Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
cites work: A note on maximizing a submodular set function subject to a knapsack constraint
cites work: Q3549686
cites work: Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
DOI: 10.1007/S10898-021-01014-1
description: scientific article; zbMATH DE number 7382627