Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
From MaRDI portal
(Redirected from Publication:408438)
Abstract: We study the problem of maximizing constrained non-monotone submodular functions and provide approximation algorithms that improve existing algorithms in terms of either the approximation factor or simplicity. Our algorithms combine existing local search and greedy based algorithms. Different constraints that we study are exact cardinality and multiple knapsack constraints. For the multiple-knapsack constraints we achieve a -factor algorithm. We also show, as our main contribution, how to use the continuous greedy process for non-monotone functions and, as a result, obtain a -factor approximation algorithm for maximization over any solvable down-monotone polytope. The continuous greedy process has been previously used for maximizing smooth monotone submodular function over a down-monotone polytope cite{CCPV08}. This implies a 0.13-approximation for several discrete problems, such as maximizing a non-negative submodular function subject to a matroid constraint and/or multiple knapsack constraints.
Recommendations
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Non-monotone submodular maximization under matroid and knapsack constraints
- Maximization of nonsubmodular functions under multiple constraints with applications
- Constrained submodular maximization via greedy local search
- Fast algorithms for maximizing monotone nonsubmodular functions
Cites work
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
- A threshold of ln n for approximating set cover
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- An improved branch \& bound method for the uncapacitated competitive location problem
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Dependent rounding and its applications to approximation algorithms
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Maximizing Non-monotone Submodular Functions
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing submodular set functions subject to multiple linear constraints
- Non-monotone submodular maximization under matroid and knapsack constraints
- Optimal approximation for the submodular welfare problem in the value oracle model
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular maximization by simulated annealing
Cited in
(13)- Improved deterministic algorithms for non-monotone submodular maximization
- Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
- scientific article; zbMATH DE number 5670654 (Why is no real title available?)
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Non-monotone submodular function maximization under \(k\)-system constraint
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- An accelerated continuous greedy algorithm for maximizing strong submodular functions
- Maximizing Non-monotone Submodular Functions
- Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
- Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint
- Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
- Maximization of nonsubmodular functions under multiple constraints with applications
- A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
This page was built for publication: Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408438)
