Abstract
We consider the problem of maximizing a monotone submodular function subject to a single knapsack constraint. We describe an algorithm that achieves a nearly-optimal 1 - 1/e - eps approximation using (1/eps)^O(1/eps^4) n log^2 n queries to the evaluation oracle for the function. Our algorithm solves the multilinear relaxation for the problem but it avoids a quadratic dependency on the number of value queries by ensuring that the solution has only O(1/eps^4) entries that are strictly fractional (not equal to 0 or 1).
This is joint work with Huy Nguyen (Northeastern University).