Submodular Maximization Subject to Matroid Intersection on the Fly

Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especially when dealing with multiple constraints. In this work, we nearly close several basic gaps in submodular maximization subject to k matroid constraints in the data stream model. We present a new hardness result showing that super polynomial memory in k is needed to obtain an o(k/log k)-approximation. This implies near optimality of prior algorithms. For the same setting, we show that one can nevertheless obtain a constant-factor approximation by maintaining a set of elements whose size is independent of the stream size. Finally, for bipartite matching constraints, a well-known special case of matroid intersection, we present a new technique to obtain hardness bounds that are significantly stronger than those obtained with prior approaches. Prior results left it open whether a 2-approximation may exist in this setting, and only a complexity-theoretic hardness of 1.91 was known. We prove an unconditional hardness of 2.69.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف30th Annual European Symposium on Algorithms, ESA 2022
المحررونShiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
ناشرSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
الصفحات52:1-52:14
عدد الصفحات14
رقم المعيار الدولي للكتب (الإلكتروني)9783959772471
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 سبتمبر 2022
منشور خارجيًانعم
الحدث30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, ألمانيا
المدة: ٥ سبتمبر ٢٠٢٢٩ سبتمبر ٢٠٢٢

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت244
رقم المعيار الدولي للدوريات (المطبوع)1868-8969

!!Conference

!!Conference30th Annual European Symposium on Algorithms, ESA 2022
الدولة/الإقليمألمانيا
المدينةBerlin/Potsdam
المدة٥/٠٩/٢٢٩/٠٩/٢٢

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

Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

بصمة

أدرس بدقة موضوعات البحث “Submodular Maximization Subject to Matroid Intersection on the Fly'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا