2026-07-22T12:29:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23147 2025-10-02T12:35:15Z ddc:004 open_access

Group Fairness and Multi-Criteria Optimization in School Assignment K. A., Santhini Munagala, Kamesh Nasre, Meghana S. Sankar, Govind School Assignment Approximation Algorithms Group Fairness We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either by concave objectives, or additional constraints on the utility of the groups. We present approximation algorithms for this assignment problem with group fairness via convex program rounding. These algorithms achieve various trade-offs between capacity violation and running time. We also show that our techniques easily extend to the setting where there are arbitrary constraints on the feasible assignment, capturing multi-criteria optimization. We present simulation results that demonstrate that the rounding methods are practical even on large problem instances, with the empirical capacity violation being much better than the theoretical bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Santhini K. A. and Kamesh Munagala and Meghana Nasre and Govind S. Sankar 2025 Is Part Of LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FORC.2025.20 urn:nbn:de:0030-drops-231471 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode