Pareto optimal matchings of students to courses in the presence of prerequisites
Pareto optimal matchings of students to courses in the presence of prerequisites
复制标题
DOI：
10.1016/j.disopt.2018.04.004
复制
发表时间：
2016-03
期刊：
影响因子：
--
通讯作者：
K. Cechlárová;B. Klaus;D. Manlove
中科院分区：
文献类型：
--
作者：
K. Cechlárová;B. Klaus;D. Manlove
我们考虑了将申请者分配到课程的问题，其中每个申请者都有一个可接受的课程子集，并且按照严格的偏好顺序进行排序。每个申请者和课程都有能力，表示可以分别分配给他们的课程和申请者的最大数量。因此，我们本质上有一个具有单边偏好的多对多二部匹配问题，它适用于大学选修课的学生分配。我们认为加性偏好和词典偏好是将对个别课程的偏好扩展到对课程捆绑的偏好的两种方法。此外，我们还关注课程有先决条件限制的情况：我们将主要将这些限制视为必修课，但我们也允许替代先决条件。对于基本问题的这些扩展，我们给出了以下算法结果，主要涉及Pareto最优匹配(POMS)的计算。首先，我们考虑强制性的先决条件。对于加性偏好，我们证明了寻找POM的问题是NP难的。另一方面，在词典偏好的情况下，基于众所周知的顺序机制，我们给出了一个寻找POM的多项式时间算法。然而，我们证明了判定给定匹配是否为帕累托最优的问题是共NP完全的。进一步证明了寻找最大基数(Pareto最优)匹配是NP难的。在可选的前提条件下，我们证明了无论是对于加性偏好还是词典偏好，找到POM都是NP难的。最后，我们考虑同条件。我们证明了，就像在强制先决条件的情况下一样，对于加性偏好，找到POM是NP困难的，尽管对于词典偏好，POM是可以在多项式时间内求解的。在后一种情况下，寻找最大基数POM的问题是NP困难的，并且很难逼近。
We consider the problem of allocating applicants to courses, where each applicant has a subset of acceptable courses that she ranks in strict order of preference. Each applicant and course has acapacity, indicating the maximum number of courses and applicants they can be assigned to, respectively. We thus essentially have a many-to-many bipartite matching problem with one-sided preferences, which has applications to the assignment of students to optional courses at a university.We consider additive preferences and lexicographic preferences as two means of extending preferences over individual courses to preferences over bundles of courses. We additionally focus on the case that courses have prerequisite constraints: we will mainly treat these constraints as compulsory, but we also allow alternative prerequisites. We further study the case where courses may be corequisites.For these extensions to the basic problem, we present the following algorithmic results, which are mainly concerned with the computation of Pareto optimal matchings (POMs). Firstly, we consider compulsory prerequisites. For additive preferences, we show that the problem of finding a POM is NP-hard. On the other hand, in the case of lexicographic preferences we give a polynomial-time algorithm for finding a POM, based on the well-known sequential mechanism. However we show that the problem of deciding whether a given matching is Pareto optimal is co-NP-complete. We further prove that finding a maximum cardinality (Pareto optimal) matching is NP-hard. Under alternative prerequisites, we show that finding a POM is NP-hard for either additive or lexicographic preferences. Finally we consider corequisites. We prove that, as in the case of compulsory prerequisites, finding a POM is NP-hard for additive preferences, though solvable in polynomial time for lexicographic preferences. In the latter case, the problem of finding a maximum cardinality POM is NP-hard and very difficult to approximate.