Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint (Q2046266)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint |
scientific article |
Statements
Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint (English)
0 references
17 August 2021
0 references
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.
0 references
submodular function
0 references
supermodular function
0 references
integer lattice
0 references
cardinality constraint
0 references
threshold greedy algorithm
0 references