Non-monotone submodular maximization under matroid and knapsack constraints
| dc.creator | Lee, Jon | |
| dc.creator | Mirrokni, Vahab | |
| dc.creator | Nagarjan, Viswanath | |
| dc.creator | Sviridenko, Maxim | |
| dc.date | 2009-02-02 | |
| dc.date.accessioned | 2026-07-07T12:37:04Z | |
| dc.date.available | 2026-07-07T12:37:04Z | |
| dc.description | Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. For the problem of maximizing a non-monotone submodular function, Feige, Mirrokni, and Vondrák recently developed a $2\over 5$-approximation algorithm \cite{FMV07}, however, their algorithms do not handle side constraints.} In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for {\em non-monotone} submodular functions. In particular, for any constant $k$, we present a $({1\over k+2+{1\over k}+ε})$-approximation for the submodular maximization problem under $k$ matroid constraints, and a $({1\over 5}-ε)$-approximation algorithm for this problem subject to $k$ knapsack constraints ($ε>0$ is any constant). We improve the approximation guarantee of our algorithm to ${1\over k+1+{1\over k-1}+ε}$ for $k\ge 2$ partition matroid constraints. This idea also gives a $({1\over k+ε})$-approximation for maximizing a {\em monotone} submodular function subject to $k\ge 2$ partition matroids, which improves over the previously best known guarantee of $\frac{1}{k+1}$. | |
| dc.identifier | https://arxiv.org/abs/0902.0353 | |
| dc.identifier | http://arxiv.org/abs/0902.0353 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/218307 | |
| dc.subject | Computational Complexity | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Non-monotone submodular maximization under matroid and knapsack constraints | |
| dc.type | text |