Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint.
Yuichi YoshidaPublished in: SIAM J. Discret. Math. (2019)
Keyphrases
- submodular functions
- greedy algorithm
- facility location problem
- knapsack problem
- energy function
- combinatorial optimization
- dynamic programming
- objective function
- upper bound
- optimal solution
- convex optimization
- facility location
- branch and bound algorithm
- markov random field
- worst case
- reinforcement learning
- neural network
- anti monotone
- theoretical guarantees
- approximation algorithms
- learning problems
- convex hull