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",
(2021),
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.