The concept of submodularity plays a vital role in combinatorial
optimization. In particular, many important optimization problems
can be cast as submodular maximization problems, including maximum
coverage, maximum facility location and Max Cut in
directed/undirected graphs.
In this paper we present the first known approximation algorithms
for the problem of maximizing a non-decreasing submodular set
function subject to multiple linear constraints. Given an oracle
for a non-decreasing submodular set function $f$ over a universe
$U$, where each element $e \in U$ is associated with a
$d$-dimensional cost vector and a $d$-dimensional budget vector
$\bL$, for some $d \geq 1$, we seek a subset of elements
$S \subseteq U$ whose total cost is at most $\bL$, such
that $f(S)$ is maximized.
We develop a framework for maximizing submodular functions subject
to $d$ linear constraints that yields a
$(1-\eps)(1-e^{-1})$-approximation to the optimum for any $\eps
> 0$, where $d >1$ is some constant. Our study is motivated from a
variant of the classical maximum coverage problem that we call
{\em maximum coverage with multiple packing constraints}. We use
our framework to obtain the same approximation ratio for this
problem. To the best of our knowledge, this is the first time the
theoretical bound of$1-e^{-1}$ is (almost) matched for both of these problems.