Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms

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

zbMATH Keywords

matroid; approximation algorithms; knapsack; cardinality; continuous greedy process; non-monotone submodular set functions

Mathematics Subject Classification ID

90C30: Nonlinear programming

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, Improved deterministic algorithms for non-monotone submodular maximization, Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint, An accelerated continuous greedy algorithm for maximizing strong submodular functions, A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint

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)