Learning to Screen
Learning to Screen
复制标题
学习筛选
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Moran
中科院分区：
文献类型：
--
作者：
Alon Cohen;Avinatan Hassidim;Haim Kaplan;Y. Mansour;S. Moran
想象一下，一家拥有多个部门的大公司计划进行大规模招聘。应聘者一个接一个地到来，公司根据她的数据(简历、技能、经验等)决定是否传唤她参加面试。该公司希望招聘最好的应聘者，同时将面试次数降至最低。我们将这样的场景建模为项目(候选人)和类别(部门)之间的分配问题：项目以在线方式逐个到达，在处理每个项目时，算法根据其价值和可以匹配的类别来决定是保留还是放弃它(这个决定是不可撤销的)。目标是保留尽可能少的项目，同时确保保留的项目集包含最佳匹配。
我们考虑这个问题的两个变体：(I)在第一个变体中，假设$n$项独立于未知分布$D$。(2)在第二个备选案文中，假定在程序开始之前，算法可以访问从同一未知分布中独立抽取的$n$个项目的训练集(例如，以前征聘季节的候选人数据)。我们给出了每个变种中保留项的最小可能数量的严格界限。这些结果表明，一个人可以在第二个变量中保留指数级更少的项目(使用训练集)。
Imagine a large firm with multiple departments that plans a large recruitment. Candidates arrive one-by-one, and for each candidate the firm decides, based on her data (CV, skills, experience, etc), whether to summon her for an interview. The firm wants to recruit the best candidates while minimizing the number of interviews. We model such scenarios as an assignment problem between items (candidates) and categories (departments): the items arrive one-by-one in an online manner, and upon processing each item the algorithm decides, based on its value and the categories it can be matched with, whether to retain or discard it (this decision is irrevocable). The goal is to retain as few items as possible while guaranteeing that the set of retained items contains an optimal matching.
We consider two variants of this problem: (i) in the first variant it is assumed that the $n$ items are drawn independently from an unknown distribution $D$. (ii) In the second variant it is assumed that before the process starts, the algorithm has an access to a training set of $n$ items drawn independently from the same unknown distribution (e.g.\ data of candidates from previous recruitment seasons). We give tight bounds on the minimum possible number of retained items in each of these variants. These results demonstrate that one can retain exponentially less items in the second variant (with the training set).
DOI：
10.1137/1.9781611974782.155
发表时间：
2017
期刊：
SIAM: ACM-SIAM Symposium on Discrete Algorithms (SODA17
影响因子：
--
作者：
Blum, Avrim;Caragiannis, Ioannis;Haghtalab, Nika;Procaccia, Ariel D.;Procaccia, Eviatar B.;Vaish, Rohit
通讯作者：
Vaish, Rohit