New performance guarantees for the greedy maximization of submodular set functions
From MaRDI portal
Publication:523157
DOI10.1007/s11590-016-1039-zzbMath1368.90124arXiv1506.00423OpenAlexW2239902130MaRDI QIDQ523157
Publication date: 20 April 2017
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.00423
Related Items (7)
Exact hypervolume subset selection through incremental computations ⋮ Two-stage non-submodular maximization ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Two-stage non-submodular maximization ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Two-stage submodular maximization under curvature ⋮ Improved algorithms for non-submodular function maximization problem
Cites Work
- Budgeted nature reserve selection with diversity feature loss and arbitrary split systems
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
- A note on maximizing a submodular set function subject to a knapsack constraint
- Maximizing Non-monotone Submodular Functions
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Matroids and the greedy algorithm
- An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
- Approximation for maximizing monotone non-decreasing set functions with a greedy method
- Unnamed Item
- Unnamed Item
This page was built for publication: New performance guarantees for the greedy maximization of submodular set functions