Name
Title | ||
|---|---|---|
A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint |
Abstract | ||
|---|---|---|
We obtain a polynomial-time deterministic (2ee−1+ϵ)-approximation algorithm for maximizing symmetric submodular functions under a budget constraint. Although there exist randomized algorithms with better expected performance, our algorithm achieves the best known factor achieved by a deterministic algorithm, improving on the previously known factor of 6. Furthermore, it is simple, combining two elegant algorithms for related problems; the local search algorithm of Feige, Mirrokni and Vondrák [1] for unconstrained submodular maximization, and the greedy algorithm of Sviridenko [2] for non-decreasing submodular maximization subject to a knapsack constraint. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.ipl.2020.106010 | Information Processing Letters |
Keywords | DocType | Volume |
Approximation algorithms,Submodular maximization,Symmetric submodular functions,Knapsack constraints | Journal | 163 |
ISSN | Citations | PageRank |
0020-0190 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| georgios amanatidis | 1 | 86 | 13.32 |
| Georgios Birmpas | 2 | 14 | 7.48 |
| Evangelos Markakis | 3 | 1225 | 86.93 |