2016/03/02 by Katarı́na Cechlárová, Cechlarova, Katarina, Bettina Klaus +3 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Advanced Algebra and Logic #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1603.00858
openalex publication_date 2016/03/02 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
We consider the problem of allocating applicants to courses, where each\napplicant has a subset of acceptable courses that she ranks in strict order of\npreference. Each applicant and course has a capacity, indicating the maximum\nnumber of courses and applicants they can be assigned to, respectively. We thus\nessentially have a many-to-many bipartite matching problem with one-sided\npreferences, which has applications to the assignment of students to optional\ncourses at a university. We consider additive preferences and lexicographic\npreferences as two means of extending preferences over individual courses to\npreferences over bundles of courses. We additionally focus on the cases that\ncourses have prerequisite constraints and where courses may be corequisites.\n For these extensions to the basic problem, we present the following\nalgorithmic results, which are mainly concerned with the computation of Pareto\noptimal matchings (POMs). Firstly, we consider compulsory prerequisites. For\nadditive preferences, we show that the problem of finding a POM is NP-hard. On\nthe other hand, in the case of lexicographic preferences we give a\npolynomial-time algorithm for finding a POM, based on the well-known sequential\nmechanism. However we show that the problem of deciding whether a given\nmatching is Pareto optimal is co-NP-complete. We further prove that finding a\nmaximum cardinality (Pareto optimal) matching is NP-hard. Under alternative\nprerequisites, we show that finding a POM is NP-hard for either additive or\nlexicographic preferences. Finally we consider corequisites. We prove that, as\nin the case of compulsory prerequisites, finding a POM is NP-hard for additive\npreferences, though solvable in polynomial time for lexicographic preferences.\nIn the latter case, the problem of finding a maximum cardinality POM is NP-hard\nand very difficult to approximate\n