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

DOI10.1016/j.orl.2011.10.002zbMath1235.90146arXiv1101.2973OpenAlexW2052876922MaRDI 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

matroidapproximation algorithmsknapsackcardinalitycontinuous greedy processnon-monotone submodular set functions

Mathematics Subject Classification ID

Nonlinear programming (90C30) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (5)

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ An accelerated continuous greedy algorithm for maximizing strong submodular functions ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint ⋮ 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)

This page was built for publication: Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms