Name
Title | ||
|---|---|---|
A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. |
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2017 | ICALP | Bottleneck,Discrete mathematics,Combinatorics,Submodular set function,Algorithm,Submodular maximization,Omega,Knapsack problem,Time complexity,Multilinear map,Mathematics,Monotone polygon |
DocType | Volume | Citations |
Journal | abs/1709.09767 | 1 |
PageRank | References | Authors |
0.35 | 7 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alina Ene | 1 | 409 | 25.47 |
| Huy L. Nguyen | 2 | 376 | 32.33 |