  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).
