![Bridging Continuous and Discrete Optimization_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Bridging%20Continuous%20and%20Discrete%20Optimization_hi-res.png.jpg?itok=b7fmT0eV)
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).