Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
From MaRDI portal
Publication:3058545
DOI10.1137/090750020zbMath1207.68445OpenAlexW2064933851MaRDI QIDQ3058545
Jon Lee, M. I. Sviridenko, Viswanath Nagarajan, Vahab S. Mirrokni
Publication date: 3 December 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/42214ef7379f192a71fe4cae313956dcd5c31bff
approximation algorithmsknapsack constraintssubmodular maximizationmatroid constraintsnonmonotone submodular functions
Related Items
Streaming Algorithms for Submodular Function Maximization ⋮ A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Maximizing Symmetric Submodular Functions ⋮ Two-stage stochastic max-weight independent set problems ⋮ Max-Cut Under Graph Constraints ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Constrained Assortment Optimization Under the Paired Combinatorial Logit Model ⋮ The Power of Subsampling in Submodular Maximization ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint ⋮ Two-stage submodular maximization under knapsack and matroid constraints ⋮ Two-stage non-submodular maximization ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ Two-stage non-submodular maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Greedy guarantees for non-submodular function maximization under independent system constraint with applications ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Inequalities on submodular functions via term rewriting ⋮ Submodular Optimization with Contention Resolution Extensions. ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ The Submodular Secretary Problem Goes Linear ⋮ Approximating minimum power edge-multi-covers ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Weakly Submodular Function Maximization Using Local Submodularity Ratio. ⋮ Supermodular covering knapsack polytope ⋮ On maximizing a monotone \(k\)-submodular function subject to a matroid constraint ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Approximability issues for unconstrained and constrained maximization of half-product related functions ⋮ Sequence submodular maximization meets streaming ⋮ Approximating graph-constrained max-cut ⋮ Constrained submodular maximization via greedy local search ⋮ Two-stage submodular maximization under curvature ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Two-stage submodular maximization under curvature ⋮ Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract) ⋮ Maximization problems of balancing submodular relevance and supermodular diversity ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Nonsubmodular constrained profit maximization from increment perspective ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ Submodular function minimization and polarity ⋮ Electrical flows over spanning trees ⋮ Unnamed Item ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
