Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol

摘要: The classical secretary problem investigates the question of how to hire best from $n$ candidates who come in a uniformly random order. In this work we investigate parallel generalizations introduced by Feldman and Tennenholtz [14]. We call it shared $Q$-queue $J$-choice $K$-best problem. problem, are evenly distributed into $Q$ queues, instead hiring one, employer wants $J$ among $K$ persons. quotas all queues. This is generalized version which has been extensively studied more practical value as characterizes situation. Although few works have done about generalization, our knowledge, no optimal deterministic protocol was known with general paper, provide an for same style $1\over e$-solution but multiple phases adaptive criteria. Our very simple efficient, show that several generalizations, such fractional exclusive can be solved optimally slight modification latter one solves open In addition, theoretical analysis two typical cases, including 1-queue 1-choice 2-queue 2-choice 2-best For former, prove lower bound $1-O(\frac{\ln^2K}{K^2})$ competitive ratio. latter, ratio $\approx0.372$ while previously result 0.356