Constrained submodular maximization via greedy local search
From MaRDI portal
Publication:2294252
DOI10.1016/j.orl.2018.11.002zbMath1476.90289arXiv1705.06319OpenAlexW2964343703MaRDI QIDQ2294252
Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai
Publication date: 10 February 2020
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.06319
Related Items (8)
A multi-pass streaming algorithm for regularized submodular maximization ⋮ On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ A constrained two-stage submodular maximization ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- On the complexity of approximating \(k\)-set packing
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- A threshold of ln n for approximating set cover
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Fast algorithms for maximizing submodular functions
- A Unified Continuous Greedy Algorithm for Submodular Maximization
This page was built for publication: Constrained submodular maximization via greedy local search