Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint (Q2046266): Difference between revisions

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.