Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

Details Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

2011-01-15

arxiv.org/abs/1101.2940v1

Computer Science

Data Structures and Algorithms

A preliminary version of this paper appeared in the Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms,

Scientific paper

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 {\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 the discrete problem. 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.

Affiliated with

Also associated with

No associations

Rating

Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack 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 Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-227861