Fall 2017

A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

Wednesday, September 13th, 2017 11:30 am12:00 pm

Add to Calendar

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).