ملخص
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, الولايات المتّحدة المدة: ٦ يناير ٢٠١٩ → ٩ يناير ٢٠١٩ |
!!Conference
!!Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|
الدولة/الإقليم | الولايات المتّحدة |
المدينة | San Diego |
المدة | ٦/٠١/١٩ → ٩/٠١/١٩ |
ملاحظة ببليوغرافية
Publisher Copyright:Copyright © 2019 by SIAM.