Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
From MaRDI portal
Publication:408438
DOI10.1016/j.orl.2011.10.002zbMath1235.90146arXiv1101.2973MaRDI QIDQ408438
Salman Fadaei, Mohammad Amin Fazli, Mohammad Ali Safari
Publication date: 5 April 2012
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.2973
matroid; approximation algorithms; knapsack; cardinality; continuous greedy process; non-monotone submodular set functions
90C30: Nonlinear programming
90C59: Approximation methods and heuristics in mathematical programming
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- An improved branch \& bound method for the uncapacitated competitive location problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
- Maximizing Non-monotone Submodular Functions
- A threshold of ln n for approximating set cover
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Dependent rounding and its applications to approximation algorithms
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Non-monotone submodular maximization under matroid and knapsack constraints
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
