Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
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.
- A note on maximizing a submodular set function subject to a knapsack constraint
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- Maximization of submodular functions: theory and enumeration algorithms
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Optimal approximation for the submodular welfare problem in the value oracle model
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Maximization problems of balancing submodular relevance and supermodular diversity
- Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
- Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
- Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
- A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
- On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice
- Profit maximization in social networks and non-monotone DR-submodular maximization
- A fast double greedy algorithm for non-monotone DR-submodular function maximization
- A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity
- A binary search double greedy algorithm for non-monotone DR-submodular maximization
- Differentially private submodular maximization with a cardinality constraint over the integer lattice
- Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
- Maximizing the ratio of monotone DR-submodular functions on integer lattice
- Maximizing the difference of DR-submodular function on the integer lattice
This page was built for publication: Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2046266)
