2026-07-22T16:00:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10629 2024-03-06T10:46:19Z ddc:004 open_access

A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint Ene, Alina Nguyen, Huy L. submodular maximization knapsack constraint fast algorithms We consider the problem of maximizing a monotone submodular function subject to a knapsack constraint. Our main contribution is an algorithm that achieves a nearly-optimal, 1 - 1/e - epsilon approximation, using (1/epsilon)^{O(1/epsilon^4)} n log^2{n} function evaluations and arithmetic operations. Our algorithm is impractical but theoretically interesting, since it overcomes a fundamental running time bottleneck of the multilinear extension relaxation framework. This is the main approach for obtaining nearly-optimal approximation guarantees for important classes of constraints but it leads to Omega(n^2) running times, since evaluating the multilinear extension is expensive. Our algorithm maintains a fractional solution with only a constant number of entries that are strictly fractional, which allows us to overcome this obstacle. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alina Ene and Huy L. Nguyen 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.53 urn:nbn:de:0030-drops-106290 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.53 eng https://creativecommons.org/licenses/by/3.0/legalcode