A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
summary
Claims a nearly-linear number of value queries (roughly N log^2 N) to get a 1 - 1/e - ε approximation for submodular maximization under a knapsack, improving the usual quadratic cost of multilinear approaches. Key tools are the multilinear relaxation + continuous greedy, lazy/density greedy, and enumerating marginal gains instead of items. The algorithm forces bounded fractionality (only O(ε^{-4}) fractional coordinates), enabling exact-preserving rounding within budget. Works theoretically but carries a very large dependence on ε (poly(1/ε) exponents like 1/ε^8 hidden).
AI-written summary · about