学生面试问题的分配策略

The Student Interview Problem and Its Allocation Strategies

就学生面试问题中的教师分配策略进行了系统的分析.首先我们分别给出并证明了在面试老师数一定,满足没有两个老师相同以及三个老师相同情形下的,可承担面试学生数的四个上界.然后提出了2种分配算法:排队算法和集合压缩算法,计算结果表明,所提算法可以很好的逼近理论上界.针对文理各半的情形,我们也同样提出并证明了类似的上界,两种分配策略同样适合文理各半的情形.在不分文理和文理各半的两种情况下,我们提出的分配策略都能很好的逼进甚至达到上界,同时也说明了我们理论界是一个很紧的上界.

We systematically analyze the strategy of student interview problem. We first obtain four upper bounds for the fixed number of teachers, without two teachers in common or three in common. Thereafter, we propose two algorithms, i.e. queue algorithm and set compression algorithm. Numerical results shows that both of them can approach even achieve the upper bounds. In the case of half arts and half science teachers, the strategies are also present good performance. In all the cases, the algorithms can approach the upper bounds, which also validate the tightness of the upper bounds.