摘要: 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, we mainly deal with one of those generalizations which is a generalization of the classical one, called shared Q-queue J-choice 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. In this talk, we provide an optimal deterministic protocol for this generalizations.The protocol is in the same style of the 1/e-solution for the classical secretary problem, but with multiple phases and adaptive criteria. The protocol is simple and efficient,and we 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.

演講者簡介: Jialin Zhang received her Ph.D. degree from Tsinghua University, Beijing, and is currently an Associate Professor at the Institute of Computing Technology, Chinese Academy of Science. Her research interests include distributed computing, social and information networks, algorithmic game theory, and combinatorial optimization.