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 paper we consider the problem of maximizing any submodular function subject to d knapsack constraints, where d is a fixed
constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through 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 the discrete problem. We use this relation to obtain an $(e^{-1}-\eps)$-approximation for the problem, and 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.