A simple O(loglog(rank))-competitive algorithm for the matroid secretary problem

Moran Feldman, Ola Svensson, Rico Zenklusen

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

Only recently, progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a O((log(rank))1/2)-competitive procedure, and Lachish (2014) later presented a O(loglog(rank))-competitive algorithm. Both these algorithms and their analyses are very involved, which is also reflected in the extremely high constants in their competitive ratios. Using different tools, we present a considerably simpler O(loglog(rank))-competitive algorithm for the matroid secretary problem. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms that are easy to analyze. Because of the simplicity of our procedure, we are also able to vastly improve on the hidden constant in the competitive ratio.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)638-650
عدد الصفحات13
دوريةMathematics of Operations Research
مستوى الصوت43
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - مايو 2018

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

Publisher Copyright:
© 2018 INFORMS.

بصمة

أدرس بدقة موضوعات البحث “A simple O(loglog(rank))-competitive algorithm for the matroid secretary problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا