[Back]


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), Yokohama, Japan; 2021-01-07 - 2021-01-15; in: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence", (2020), ISBN: 978-0-9992411-6-5; 1 - 7.



English abstract:
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:
https://publik.tuwien.ac.at/files/publik_293438.pdf


Created from the Publication Database of the Vienna University of Technology.