We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint (SMKP) . The input is a set I of items, each associated with a non-negative weight, and a set of bins , each having a capacity . Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a  subset of items A \subseteq I and a packing of the items in the bins , such that f(A) is maximized. SMKP is a natural extension of both Multiple Knapsack and the problem of monotone submodular maximization subject to a knapsack constraint. Our main result is a nearly optimal polynomial time (1-e^{-1}- \varepsilon \eps )-approximation algorithm for the problem, for any \varepsilon \eps >0. Our algorithm relies on a  refined analysis of techniques for constrained submodular optimization combined with sophisticated application of tools used in the development of approximation schemes for packing problems .
We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint . The input is a set I of items, each has a non-negative weight, and a set of bins of arbitrary capacities . Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a packing of a subset of items A \subseteq I in the bins such that f(A) is maximized. Our main result is an almost optimal polynomial time (1-e^{-1}- \eps )-approximation algorithm for the problem, for any \eps >0. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints .
D
(SMKP)
R
associated with
has
R
, each having a capacity
of arbitrary capacities
A
packing of a
D
and a packing of the items
D
,
D
SMKP is a natural extension of both Multiple Knapsack and the problem of monotone submodular maximization subject to a knapsack constraint.
R
a nearly
an almost
D
\varepsilon
D
\varepsilon
R
Our
The
A
structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a
R
constrained submodular optimization combined with sophisticated application of tools used in the development of approximation schemes for packing problems
submodular optimization subject to knapsack constraints