Building a good team: Secretary problems and the supermodular degree

Moran Feldman, Rani Izsak

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


In the (classical) secretary problem, one has to hire the best among n candidates. The candidates are interviewed, one at a time, at a uniformly random order, and one has to decide on the spot, whether to hire a candidate or continue interviewing. It is well known that the best candidate can be hired with a probability of 1/e (Dynkin, 1963). Recent works extend this problem to settings in which multiple candidates can be hired, subject to some constraint. Here, one wishes to hire a set of candidates maximizing a given objective set function. Almost all extensions considered in the literature assume the objective set function is either linear or submodular. Unfortunately, real world functions might not have either of these properties. Consider, for example, a scenario where one hires researchers for a project. Indeed, it can be that some researchers can substitute others for that matter. However, it can also be that some combinations of researchers result in synergy (see, e.g., Woolley et al., Science 2010, for a study on collective intelligence). The first phenomenon can be modeled by a submoudlar set function, while the latter cannot. In this work, we study the secretary problem with an arbitrary non-negative monotone valuation function, subject to a general matroid constraint. One can prove that, generally, only very poor results can be obtained for this class of objective functions. We tackle this hardness by combining the following: (1) Parametrizing our algorithms by the supermodular degree of the objective function (defined by Feige and Izsak, ITCS 2013), which, roughly speaking, measures the distance of a function from being submodular. (2) Suggesting an (arguably) natural model that permits approximation guarantees that are polynomial in the supermodular degree (as opposed to the standard model which allows only exponential guarantees). Our algorithms learn the input by running a non-trivial estimation algorithm on a portion of it whose size depends on the supermodular degree. We also provide better approximation guarantees for the special case of a uniform matroid constraint. To the best of our knowledge, our results represent the first algorithms for a secretary problem handling arbitrary non-negative monotone valuation functions.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
المحررونPhilip N. Klein
ناشرAssociation for Computing Machinery
عدد الصفحات20
رقم المعيار الدولي للكتب (الإلكتروني)9781611974782
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2017
الحدث28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, أسبانيا
المدة: ١٦ يناير ٢٠١٧١٩ يناير ٢٠١٧

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

الاسمProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
مستوى الصوت0


!!Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

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

Publisher Copyright:
Copyright © by SIAM.


أدرس بدقة موضوعات البحث “Building a good team: Secretary problems and the supermodular degree'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا