Fast algorithms for maximizing submodular functions
From MaRDI portal
Publication:5384072
DOI10.1137/1.9781611973402.110zbMATH Open1422.68286OpenAlexW4231490457MaRDI QIDQ5384072FDOQ5384072
Authors: Ashwinkumar Badanidiyuru, Jan Vondrák 
Publication date: 20 June 2019
Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611973402.110
Recommendations
- Fast algorithms for maximizing monotone nonsubmodular functions
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Non-monotone submodular maximization under matroid and knapsack constraints
- Fast algorithms for maximizing monotone nonsubmodular functions
- Maximizing a monotone submodular function subject to a matroid constraint
Cited In (86)
- Improved deterministic algorithms for non-monotone submodular maximization
- Adaptive algorithms on maximizing monotone nonsubmodular functions
- Fast deterministic algorithms for non-submodular maximization with strong performance guarantees
- Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
- Efficient processing of \(k\)-regret minimization queries with theoretical guarantees
- A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities
- Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
- Efficient algorithms for \(k\)-submodular function maximization with \(p\)-system and \(d\)-knapsack constraint
- Submodular Maximization Subject to a Knapsack Constraint Under Noise Models
- An accelerated deterministic algorithm for maximizing monotone submodular minus modular function with cardinality constraint
- Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
- Seeding with costly network information
- New approximations for monotone submodular maximization with knapsack constraint
- An efficient branch-and-cut algorithm for submodular function maximization
- Differentially private submodular maximization with a cardinality constraint over the integer lattice
- A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity
- The Frank-Wolfe algorithm: a short introduction
- Optimization with demand oracles
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- A Framework for the Secretary Problem on the Intersection of Matroids
- Algorithms for covering multiple submodular constraints and applications
- An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- On multiplicative weight updates for concave and submodular function maximization
- Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Maximum coverage with cluster constraints: an LP-based approximation technique
- Submodular maximization with cardinality constraints
- Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint
- Guess free maximization of submodular and linear sums
- Algorithms for maximizing monotone submodular function minus modular function under noise
- Better streaming algorithms for the maximum coverage problem
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
- A faster strongly polynomial time algorithm for submodular function minimization
- Optimal approximation for the submodular welfare problem in the value oracle model
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- Submodular maximization by simulated annealing
- A provably fast linear-expected-time maxima-finding algorithm
- Ranking with submodular functions on a budget
- Robust Adaptive Submodular Maximization
- Structured Robust Submodular Maximization: Offline and Online Algorithms
- An accelerated continuous greedy algorithm for maximizing strong submodular functions
- Measured continuous greedy with differential privacy
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
- Non-submodular streaming maximization with minimum memory and low adaptive complexity
- Maximizing a monotone submodular function subject to a matroid constraint
- Constrained submodular maximization via greedy local search
- Distributed submodular maximization
- Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
- Techniques for submodular maximization
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
- Subdeterminant maximization via nonconvex relaxations and anti-concentration
- Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms
- Guess free maximization of submodular and linear sums
- Generalized budgeted submodular set function maximization
- Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
- \(k\)-submodular maximization with two kinds of constraints
- Robust monotone submodular function maximization
- The power of subsampling in submodular maximization
- Faster and simpler sketches of valuation functions
- A refined analysis of submodular greedy
- Efficient Submodular Function Maximization under Linear Packing Constraints
- Stability and recovery for independence systems
- Streaming algorithms for submodular function maximization
- Multi-pass streaming algorithms for monotone submodular function maximization
- Fast algorithms for maximizing monotone nonsubmodular functions
- Fast algorithms for maximizing monotone nonsubmodular functions
- Siting renewable power generation assets with combinatorial optimisation
- Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Efficient approximation algorithms for maximum coverage with group budget constraints
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- Non-submodular maximization with matroid and knapsack constraints
- Practical budgeted submodular maximization
- General bounds for incremental maximization
- Monotone submodular maximization over the bounded integer lattice with cardinality constraints
- A fast double greedy algorithm for non-monotone DR-submodular function maximization
- A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
- Tight approximation for unconstrained XOS maximization
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Private non-monotone submodular maximization
- Improved deterministic algorithms for non-monotone submodular maximization
- New performance guarantees for the greedy maximization of submodular set functions
- Optimization with uniform size queries
This page was built for publication: Fast algorithms for maximizing submodular functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384072)
