The Student/Project Allocation problem with group projects.
Ashwin Arulselvan, Ágnes Cseh, Jannik Matuschke · arXiv (Cornell University) · 2014
We are given a project-based university course, where our task is to assign students to suitable projects. In the Student/Project Allocation problem, or shortly SPA, each student submits a weighted list of their acceptable projects, and likewise, a set of assignable students is given to each project. Moreover, some projects are equipped with upper and lower quotas with regards to the number of students assigned to them. The quota requirement is strict: projects not reaching their lower quotas must be closed entirely. The challenge is to find a b-matching of maximum weight observing the lower quotas. In our present work we show that finding such a maximum weight matching is an NP-complete task even if all students mark at most two projects and all projects have upper and lower quota three. Moreover, we also prove that if no upper quota is larger than two, the problem immediately becomes polynomially tractable. For the general case, an approximation algorithm is presented that reaches the best possible ratio -- due to inapproximability bounds -- expressed in various terms.