Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
J. Chen, R. Ganian, T. Hamm:
"Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP";
Vortrag: International Joint Conference on Artificial Intelligence (IJCAI),
Yokohama, Japan;
07.01.2021
- 15.01.2021; in: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence",
(2021),
ISBN: 978-0-9992411-6-5;
S. 1
- 7.
Kurzfassung englisch:
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.
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_293438.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.