Pareto optimal matchings of students to courses in the presence of prerequisites

DOI10.1016/J.DISOPT.2018.04.004MaRDI QIDQ1662656zbMATH OpenOpenAlexWikidataFDO

Authors Bettina Klaus, Katarina Cechlárová, David F. Manlove

Publication date 20 August 2018

Published in Discrete Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1603.00858

zbMATH Keywords

Pareto optimalityNP-hardnesssequential mechanismcourse allocationprerequisites

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Matching models (91B68)

Abstract: 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 a capacity, 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 cases that courses have prerequisite constraints and 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

Recommendations

• Pareto optimal matchings with lower quotas
• Pareto optimality in many-to-many matching problems
• Pareto optimal matchings in many-to-many markets with ties
• Pareto optimal matchings in many-to-many markets with ties
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Class of Sequential Games
• A note on object allocation under lexicographic preferences
• A tale of two mechanisms: Student placement
• Algorithms and Computation
• Axioms for Lexicographic Preferences
• Complexity of Scheduling under Precedence Constraints
• Job Matching, Coalition Formation, and Gross Substitutes
• Matching with quorums
• Matching with sizes (or scheduling with processing set restrictions)
• Pareto optimal matchings in many-to-many markets with ties
• Pareto optimality in many-to-many matching problems
• Queue allocation of indivisible goods
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Reducibility among combinatorial problems
• Serial dictatorship and Pareto optimality
• Some simplified NP-complete graph problems
• Strategy-proofness, solidarity, and consistency for multiple assignment problems
• The college admissions problem is not equivalent to the marriage problem

Cited in

(3)

• Optimum allocation of places to students in a national university system
• Pareto optimal matchings with lower quotas
• Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation

This page was built for publication: Pareto optimal matchings of students to courses in the presence of prerequisites

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662656)