Header menu link for other important links
X
Student Course Allocation with Constraints
Published in Springer
2019
Volume: 11544 LNCS
   
Pages: 51 - 68
Abstract
Real-world matching scenarios, like the matching of students to courses in a university setting, involve complex downward-feasible constraints like credit limits, time-slot constraints for courses, basket constraints (say, at most one humanities elective for a student), in addition to the preferences of students over courses and vice versa, and class capacities. We model this problem as a many-to-many bipartite matching problem where both students and courses specify preferences over each other and students have a set of downward-feasible constraints. We propose an Iterative Algorithm Framework that uses a many-to-one matching algorithm and outputs a many-to-many matching that satisfies all the constraints. We prove that the output of such an algorithm is Pareto-optimal from the student-side if the many-to-one algorithm used is Pareto-optimal from the student side. For a given matching, we propose a new metric called the Mean Effective Average Rank (MEAR), which quantifies the goodness of allotment from the side of the students or the courses. We empirically evaluate two many-to-one matching algorithms with synthetic data modeled on real-world instances and present the evaluation of these two algorithms on different metrics including MEAR scores, matching size and number of unstable pairs. © 2019, Springer Nature Switzerland AG.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer
ISSN03029743
Open AccessNo
Concepts (11)
  •  related image
    Iterative methods
  •  related image
    Pareto principle
  •  related image
    Bipartite matching problems
  •  related image
    COURSE ALLOCATION
  •  related image
    Iterative algorithm
  •  related image
    MANY TO MANY
  •  related image
    MATCHING ALGORITHM
  •  related image
    Pareto-optimal
  •  related image
    Synthetic data
  •  related image
    UNIVERSITY SETTINGS
  •  related image
    Students