2:30~3:00pm, Tea, Coffee, and Cookie

The classical secretary problem investigates the question of how to hire the best secretary from n candidates who come in a uniformly random order.
Many generalizations have been proposed and studied since the problem was introduced.
In this talk I will mainly deal with one of those generalizations which is called shared Q-queue Jchoice
K-best secretary problem. In this problem, n candidates are evenly distributed into Q queues, and instead of hiring the best one, the employer wants to hire J candidates among the best K persons from all candidates.
The J quotas are shared by all queues. This problem is a generalized version of J-choice K-best problem which has been extensively studied and it has more practice value due to the parallelism.
Although a few of works have been done about this generalization, to the best of our knowledge, no optimal deterministic protocol was known for the classical discrete model with multiple queues. In this talk, I will provide an optimal deterministic protocol for this generalization. The protocol is in the same style of the 1/esolution for the classical secretary problem, but with multiple phases and adaptive criteria. The protocol is simple and efficient, and I will show that several generalizations, such as the fractional J-choice K-best secretary problem and exclusive Q-queue J-choice K-best secretary problem, can be solved optimally by this protocol with slight modification.
This is a joint work with Jia Zhang and Jialin Zhang.