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, الولايات المتّحدة
المدة: ٦ يناير ٢٠١٩٩ يناير ٢٠١٩

!!Conference

!!Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
الدولة/الإقليمالولايات المتّحدة
المدينةSan Diego
المدة٦/٠١/١٩٩/٠١/١٩

ملاحظة ببليوغرافية

Publisher Copyright:
Copyright © 2019 by SIAM.

بصمة

أدرس بدقة موضوعات البحث “Deterministic (1/2 + ε)-approximation for submodular maximization over a matroid'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا