2014/05/23 by Xiaoming Sun, Jia Zhang, Sun, Xiaoming +3
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC #cs.DS #cs.GT
paper · pdf · doi:10.48550/arxiv.1405.5975
This work is accepted by ISAAC 2014
openalex publication_date 2014/05/23 · arxiv created 2014/09/17 · arxiv updated 2014/09/18 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The classical secretary problem investigates the question of how to hire the best secretary from n candidates who come in a uniformly random order. In this work we investigate a parallel generalizations of this problem introduced by Feldman and Tennenholtz [14]. We call it 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. 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 practical value as it characterizes the parallel situation. Although a few of works have been done about this generalization, to the best of our knowledge, no optimal deterministic protocol was known with general Q queues. In this paper, we provide an optimal deterministic protocol for this problem. The protocol is in the same style of the 1\over e-solution for the classical secretary problem, but with multiple phases and adaptive criteria. Our protocol is very 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 with slight modification and the latter one solves an open problem of Feldman and Tennenholtz [14]. In addition, we provide theoretical analysis for two typical cases, including the 1-queue 1-choice K-best problem and the shared 2-queue 2-choice 2-best problem. For the former, we prove a lower bound 1-O((ln2K)/(K2)) of the competitive ratio. For the latter, we show the optimal competitive ratio is ≈0.372 while previously the best known result is 0.356 [14].