Efficient Submodular Function Maximization under Linear Packing Constraints

Details Efficient Submodular Function Maximization under Linear Packing Constraints Efficient Submodular Function Maximization under Linear Packing Constraints

2010-07-21

arxiv.org/abs/1007.3604v1

Computer Science

Data Structures and Algorithms

14 pages

Scientific paper

We study the problem of maximizing a monotone submodular set function subject to linear packing constraints. An instance of this problem consists of a matrix $A \in [0,1]^{m \times n}$, a vector $b \in [1,\infty)^m$, and a monotone submodular set function $f: 2^{[n]} \rightarrow R_+$. The objective is to find a set $S$ that maximizes $f(S)$ subject to $A x_{S} \leq b$. Here, $x_S$ stands for the characteristic vector of the set $S$. A well-studied special case of this problem is when the objective function $f$ is linear. This special case captures the class of packing integer programs. Our main contribution is an efficient combinatorial algorithm that achieves an approximation ratio of $\Omega(1 / m^{1/W})$, where $W = \min\{b_i / A_{ij} : A_{ij} > 0\}$ is the width of the packing constraints. This result matches the best known performance guarantee for the linear case. One immediate corollary of this result is that the algorithm under consideration achieves constant factor approximation when the number of constraints is constant or when the width of the packing constraints is sufficiently large. This motivates us to study the large width setting, trying to determine its exact approximability. We develop an algorithm that has an approximation ratio of $(1 - \epsilon)(1 - 1/e)$ when $W = \Omega(\ln m / \epsilon^2)$. This result (almost) matches the theoretical lower bound of $1 - 1/e$, which already holds for maximizing a monotone submodular function subject to a cardinality constraint.

Affiliated with

Also associated with

No associations

Rating

Efficient Submodular Function Maximization under Linear Packing Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Submodular Function Maximization under Linear Packing Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Submodular Function Maximization under Linear Packing Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183570