Talks and Poster Presentations (with Proceedings-Entry):
J. Chen, R. Ganian, T. Hamm:
"Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP";
Talk: International Joint Conference on Artificial Intelligence (IJCAI),
- 2021-01-15; in: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence",
Weinvestigatethefollowingmany-to-onestable matching problem with diversity con-straints (SMTI-DIVERSE): Given a set of studentsand a set of colleges which have preferences overeach other, where the students have overlappingtypes, and the colleges each have a total capacityas well as quotas for individual types (the diversityconstraints), is there a matching satisfying alldiversity constraints such that no unmatchedstudent-college pair has an incentive to deviate?SMTI-DIVERSEis known to be NP-hard. How-ever, as opposed to the NP-membership claims inthe literature[Azizet al., 2019; Huang, 2010], weprove that it is beyond NP: it is complete for thecomplexity class P2. In addition, we provide acomprehensive analysis of the problemīs complex-ity from the viewpoint of natural restrictions to in-puts and obtain new algorithms for the problem.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.