Technical Report MSC-2011-08

Title: Submodular and Linear Maximization with Knapsack Constraints
Authors: Ariel Kulik
Supervisors: Hadas Shachnai
Abstract: Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location and marketing over social networks.

In this work we consider the problem of maximizing any submodular function subject to $d$ knapsack constraints, where $d$ is a fixed constant. For short, we call this problem $\SUB$. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through {\em extension by expectation} of the submodular function. Formally, we show that, for any non-negative submodular function, an $\alpha$-approximation algorithm for the continuous relaxation implies a randomized $(\alpha - \eps)$-approximation algorithm for $\SUB$. We use this relation to improve the best known approximation ratio for the problem to $1/4- \eps$, for any $\eps > 0$, and to obtain a nearly optimal $(1-e^{-1}-\eps)-$approximation ratio for the monotone case, for any $\eps>0$. We further show that the probabilistic domain defined by a continuous solution can be reduced to yield a polynomial size domain, given an oracle for the extension by expectation. This leads to a deterministic version of our technique.

Our approach has a potential of wider applicability, which we demonstrate on the examples of the Generalized Assignment Problem and Maximum Coverage with additional knapsack constraints.

We also consider the special case of $\SUB$ in which the objective function is {\em linear}. In this case, our problem reduces to the classic {\em d-dimensional knapsack} problem. It is known that, unless $P=NP$, there is no {\em fully polynomial time approximation scheme} for $d$-dimensional knapsack, already for $d=2$. The best known result is a {\em polynomial time approximation scheme (PTAS)} due to Frieze and Clarke (\textit{European J. of Operational Research, 100--109, 1984}) for the case where $d \geq 2$ is some fixed constant. A fundamental open question is whether the problem admits an {\em efficient PTAS (EPTAS)}.

We resolve this question by showing that there is no EPTAS for $d$-dimensional knapsack, already for $d=2$, unless $W[1]=FPT$. Furthermore, we show that unless all problems in SNP are solvable in sub-exponential time, there is no approximation scheme for two-dimensional knapsack whose running time is $f(1/\eps) |\cI|^{o(\sqrt{1/\eps})}$, for any function $f$. Together, the two results suggest that a significant improvement over the running time of the scheme of Frieze and Clarke is unlikely to exist.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2011
To the main CS technical reports page

Computer science department, Technion