Unconstrained submodular maximization with constant adaptive complexity

Lin Chen, Moran Feldman, Amin Karbasi

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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 יוני 201926 יוני 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/1926/06/19

הערה ביבליוגרפית

Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Unconstrained submodular maximization with constant adaptive complexity'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי