Document Open Access Logo

An Algorithmic Approach to Address Course Enrollment Challenges

Authors Arpita Biswas , Yiduo Ke , Samir Khuller , Quanquan C. Liu

PDF
Thumbnail PDF

File

LIPIcs.FORC.2023.8.pdf
  • Filesize: 0.9 MB
  • 23 pages

Document Identifiers

Author Details

Arpita Biswas
  • Harvard University, Cambridge, MA, USA
Yiduo Ke
  • Northwestern University, Evanston, IL, USA
Samir Khuller
  • Northwestern University, Evanston, IL, USA
Quanquan C. Liu
  • Northwestern University, Evanston, IL, USA

Funding

Samir Khuller and Yiduo Ke gratefully acknowledge support from NSF-Award 2216970 (IDEAL Institute).

Acknowledgements

We thank Prahlad Narasimhan Kasthurirangan for pointing us to a relevant reference for one of the problems we consider.

Cite As Get BibTex

Arpita Biswas, Yiduo Ke, Samir Khuller, and Quanquan C. Liu. An Algorithmic Approach to Address Course Enrollment Challenges. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.FORC.2023.8

Abstract

Massive surges of enrollments in courses have led to a crisis in several computer science departments - not only is the demand for certain courses extremely high from majors, but the demand from non-majors is also very high. Much of the time, this leads to significant frustration on the part of the students, and getting seats in desired courses is a rather ad-hoc process. One approach is to first collect information from students about which courses they want to take and to develop optimization models for assigning students to available seats in a fair manner. What makes this problem complex is that the courses themselves have time conflicts, and the students have credit caps (an upper bound on the number of courses they would like to enroll in). We model this problem as follows. We have n agents (students), and there are "resources" (these correspond to courses). Each agent is only interested in a subset of the resources (courses of interest), and each resource can only be assigned to a bounded number of agents (available seats). In addition, each resource corresponds to an interval of time, and the objective is to assign non-overlapping resources to agents so as to produce "fair and high utility" schedules.
In this model, we provide a number of results under various settings and objective functions. Specifically, in this paper, we consider the following objective functions: total utility, max-min (Santa Claus objective), and envy-freeness. The total utility objective function maximizes the sum of the utilities of all courses assigned to students. The max-min objective maximizes the minimum utility obtained by any student. Finally, envy-freeness ensures that no student envies another student’s allocation. Under these settings and objective functions, we show a number of theoretical results. Specifically, we show that the course allocation under the time conflicts problem is NP-complete but becomes polynomial-time solvable when given only a constant number of students or all credits, course lengths, and utilities are uniform. Furthermore, we give a near-linear time algorithm for obtaining a constant 1/2-factor approximation for the general maximizing total utility problem when utility functions are binary. In addition, we show that there exists a near-linear time algorithm that obtains a 1/2-factor approximation on total utility and a 1/4-factor approximation on max-min utility when given uniform credit caps and uniform utilities. For the setting of binary valuations, we show three polynomial time algorithms for 1/2-factor approximation of total utility, envy-freeness up to one item, and a constant factor approximation of the max-min utility value when course lengths are within a constant factor of each other. Finally, we conclude with experimental results that demonstrate that our algorithms yield high-quality results in real-world settings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • fairness
  • allocation
  • matching
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Fair course allocation implementations. URL: https://github.com/yiduoke/CS-499-Khuller.
  2. Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J Schulman, and Orli Waarts. Fairness in scheduling. Journal of Algorithms, 29(2):306-357, 1998. Google Scholar
  3. Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC '06, pages 31-40, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1132516.1132522.
  4. Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and efficient allocations for matroid rank valuations. ACM Transactions on Economics and Computation, 9(4):1-41, 2021. Google Scholar
  5. Mohamed Bendraouche, Mourad Boudhar, and Ammar Oulamara. Scheduling: Agreement graph vs resource constraints. European Journal of Operational Research, 240(2):355-360, 2015. Google Scholar
  6. Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. The price of envy-freeness in machine scheduling. In Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II 39, pages 106-117. Springer, 2014. Google Scholar
  7. Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 91-97, 2018. Google Scholar
  8. Hans L Bodlaender and Fedor V Fomin. Equitable colorings of bounded treewidth graphs. Theoretical Computer Science, 349(1):22-30, 2005. Google Scholar
  9. Hans L Bodlaender, Klaus Jansen, and Gerhard J Woeginger. Scheduling with incompatible jobs. Discrete Applied Mathematics, 55(3):219-232, 1994. Google Scholar
  10. Flavia Bonomo, Sara Mattia, and Gianpaolo Oriolo. Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem. Theoretical Computer Science, 412(45):6261-6268, 2011. Google Scholar
  11. Peter Brucker and L. Nordmann. The k-track assignment problem. Computing, 52(2):97-122, 1994. URL: https://doi.org/10.1007/BF02238071.
  12. Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. Google Scholar
  13. Yinhui Cai, Guangting Chen, Yong Chen, Randy Goebel, Guohui Lin, Longcheng Liu, and An Zhang. Approximation algorithms for two-machine flow-shop scheduling with a conflict graph. In Computing and Combinatorics: 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings 24, pages 205-217. Springer, 2018. Google Scholar
  14. Martin C. Carlisle and Errol L. Lloyd. On the k-coloring of intervals. Discrete Applied Mathematics, 59(3):225-235, 1995. URL: https://doi.org/10.1016/0166-218X(95)80003-M.
  15. Nina Chiarelli, Matjaž Krnc, Martin Milanič, Ulrich Pferschy, Nevena Pivač, and Joachim Schauer. Fair allocation of indivisible items with conflict graphs. Algorithmica, pages 1-31, 2022. Google Scholar
  16. Sami Davies, Thomas Rothvoss, and Yihao Zhang. A tale of santa claus, hypergraphs and matroids. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2748-2757. SIAM, 2020. Google Scholar
  17. Colin Fisher. Resource allocation in the public sector: Values, priorities and markets in the management of public services. Routledge, 2002. Google Scholar
  18. Frédéric Gardi. Mutual exclusion scheduling with interval graphs or related classes. part ii. Discrete applied mathematics, 156(5):794-812, 2008. Google Scholar
  19. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition, 1979. URL: http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455.
  20. Guilherme C.M. Gomes and Vinicius F. dos Santos. Kernelization results for equitable coloring⁎⁎this work was partially supported by capes, cnpq, and fapemig. Procedia Computer Science, 195:59-67, 2021. Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium. URL: https://doi.org/10.1016/j.procs.2021.11.011.
  21. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL: https://www.gurobi.com.
  22. Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using NetworkX. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11-15, Pasadena, CA USA, 2008. Google Scholar
  23. Pierre Hansen, Alain Hertz, and Julio Kuplinsky. Bounded vertex colorings of graphs. Discrete Mathematics, 111(1-3):305-312, 1993. Google Scholar
  24. Halvard Hummel and Magnus Lie Hetland. Fair allocation of conflicting items. Autonomous Agents and Multi-Agent Systems, 36(1):8, 2022. Google Scholar
  25. Sungjin Im and Benjamin Moseley. Fair scheduling via iterative quasi-uniform sampling. SIAM Journal on Computing, 49(3):658-680, 2020. Google Scholar
  26. Klaus Jansen. The mutual exclusion scheduling problem for permutation and comparability graphs. Information and Computation, 180(2):71-81, 2003. Google Scholar
  27. Henry A Kierstead, Alexandr V Kostochka, Marcelo Mydlarz, and Endre Szemerédi. A fast algorithm for equitable coloring. Combinatorica, 30(2):217-224, 2010. Google Scholar
  28. Jon Kleinberg and Éva Tardos. Algorithm Design. Addison Wesley, 2006. Google Scholar
  29. Daniel Kowalczyk and Roel Leus. An exact algorithm for parallel machine scheduling with conflicts. Journal of Scheduling, 20(4):355-372, 2017. Google Scholar
  30. Bo Li, Minming Li, and Ruilong Zhang. Fair allocation with interval scheduling constraints, 2021. URL: https://doi.org/10.48550/arXiv.2107.11648.
  31. Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004. Google Scholar
  32. Amin Mallek and Mourad Boudhar. Scheduling on uniform machines with a conflict graph: complexity and resolution. International Transactions in Operational Research, 2022. Google Scholar
  33. Jakub Marecek and Andrew J Parkes. Semidefinite programming in timetabling and mutual-exclusion scheduling. arXiv preprint, 2019. URL: https://doi.org/10.48550/arXiv.1904.03539.
  34. Vignesh Viswanathan and Yair Zick. Yankee swap: a fast and simple fair allocation mechanism for matroid rank valuations. arXiv preprint, 2022. URL: https://doi.org/10.48550/arXiv.2206.08495.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact