Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation.
Aviad RubinsteinJunyao ZhaoPublished in: ICALP (2022)
Keyphrases
- submodular functions
- greedy algorithm
- facility location problem
- energy function
- combinatorial optimization
- convex optimization
- objective function
- diminishing returns
- approximation algorithms
- higher order
- dynamic programming
- probabilistic model
- markov random field
- learning problems
- theoretical guarantees
- facility location