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

DOI10.1016/J.ORL.2011.10.002zbMATH Open1235.90146arXiv1101.2973OpenAlexW2052876922MaRDI QIDQ408438FDOQ408438

Authors: Salman Fadaei, MohammadAmin Fazli, MohammadAli Safari 

Publication date: 5 April 2012

Published in: Operations Research Letters (Search for Journal in Brave)

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 $(0.25-2epsilon)$-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 $0.13$-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.

Full work available at URL: https://arxiv.org/abs/1101.2973

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

zbMATH Keywords

approximation algorithmsmatroidcardinalityknapsackcontinuous greedy processnon-monotone submodular set functions

Mathematics Subject Classification ID

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

Cites Work

• A threshold of ln n for approximating set cover
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Maximizing a monotone submodular function subject to a matroid constraint
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Dependent rounding and its applications to approximation algorithms
• Non-monotone submodular maximization under matroid and knapsack constraints
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Maximizing submodular set functions subject to multiple linear constraints
• An improved branch \& bound method for the uncapacitated competitive location problem
• Maximizing Non-monotone Submodular Functions
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
• Optimal approximation for the submodular welfare problem in the value oracle model
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• 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
• Title not available (Why is that?)
• 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)