Deterministic (1/2 + ε)-approximation for submodular maximization over a matroid

Niv Buchbinder, Moran Feldman, Mohit Garg

פרסום מחקרי: תוצר מחקר מכנסהרצאהביקורת עמיתים

תקציר

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 ינו׳ 20199 ינו׳ 2019

כנס

כנס30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
מדינה/אזורארצות הברית
עירSan Diego
תקופה6/01/199/01/19

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

Publisher Copyright:
Copyright © 2019 by SIAM.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Deterministic (1/2 + ε)-approximation for submodular maximization over a matroid'. יחד הם יוצרים טביעת אצבע ייחודית.

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