תקציר
In this paper, we consider the unconstrained submodular maximization problem. We propose the first algorithm for this problem that achieves a tight (1/2 − ε)-approximation guarantee using Õ(ε−1) adaptive rounds and a linear number of function evaluations. No previously known algorithm for this problem achieves an approximation ratio better than 1/3 using less than Ω(n) rounds of adaptivity, where n is the size of the ground set. Moreover, our algorithm easily extends to the maximization of a non-negative continuous DR-submodular function subject to a box constraint, and achieves a tight (1/2 − ε)-approximation guarantee for this problem while keeping the same adaptive and query complexities.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |
עורכים | Moses Charikar, Edith Cohen |
מוציא לאור | Association for Computing Machinery |
עמודים | 102-113 |
מספר עמודים | 12 |
מסת"ב (אלקטרוני) | 9781450367059 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 23 יוני 2019 |
אירוע | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, ארצות הברית משך הזמן: 23 יוני 2019 → 26 יוני 2019 |
סדרות פרסומים
שם | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|
ISSN (מודפס) | 0737-8017 |
כנס
כנס | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 |
---|---|
מדינה/אזור | ארצות הברית |
עיר | Phoenix |
תקופה | 23/06/19 → 26/06/19 |
הערה ביבליוגרפית
Publisher Copyright:© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.