2017/09/27 by Alina Ene, Ene, Alina, Huy L. Nguyên +1 · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1709.09767
openalex publication_date 2017/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of maximizing a monotone submodular function subject\nto a knapsack constraint. Our main contribution is an algorithm that achieves a\nnearly-optimal, 1 - 1/e - \ε approximation, using\n(1/\ε)O(1/\ε4) n \log2n function evaluations and\narithmetic operations. Our algorithm is impractical but theoretically\ninteresting, since it overcomes a fundamental running time bottleneck of the\nmultilinear extension relaxation framework. This is the main approach for\nobtaining nearly-optimal approximation guarantees for important classes of\nconstraints but it leads to \Ω(n2) running times, since evaluating the\nmultilinear extension is expensive. Our algorithm maintains a fractional\nsolution with only a constant number of entries that are strictly fractional,\nwhich allows us to overcome this obstacle.\n