תקציר
We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2 + ε)-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the 1/2-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsely and Fisher in 1978.
שפה מקורית | אנגלית |
---|---|
עמודים | 241-254 |
מספר עמודים | 14 |
סטטוס פרסום | פורסם - 2019 |
אירוע | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, ארצות הברית משך הזמן: 6 ינו׳ 2019 → 9 ינו׳ 2019 |
כנס
כנס | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|
מדינה/אזור | ארצות הברית |
עיר | San Diego |
תקופה | 6/01/19 → 9/01/19 |
הערה ביבליוגרפית
Publisher Copyright:Copyright © 2019 by SIAM.