Academic Journal
Strong stability in the hospitals/residents problem
| العنوان: | Strong stability in the hospitals/residents problem |
|---|---|
| المؤلفون: | Robert W. Irving, David F. Manlove, Y Scott |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://www.dcs.gla.ac.uk/publications/PAPERS/6769/TR-2002-123.pdf. |
| بيانات النشر: | Springer-Verlag |
| سنة النشر: | 2003 |
| المجموعة: | CiteSeerX |
| مصطلحات موضوعية: | stable matching problem, strong stability, hospitals/residents problem, polynomial-time algorithm, lower bound |
| الوصف: | We study a version of the well-known Hospitals/Residents problem in which participants ’ preferences may involve ties or other forms of indifference. In this context, we investigate the concept of strong stability, arguing that this may be the most appropriate and desirable form of stability in many practical situations. When the indifference is in the form of ties, we describe an O(a 2) algorithm to find a strongly stable matching, if one exists, where a is the number of mutually acceptable (resident,hospital) pairs. We also give a lower bound in this case in terms of the complexity of determining whether a bipartite graph contains a perfect matching. By way of contrast, we prove that it becomes NP-complete to determine whether a strongly stable matching exists if the preferences are allowed to be arbitrary partial orders. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.2872; http://www.dcs.gla.ac.uk/publications/PAPERS/6769/TR-2002-123.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.2872 http://www.dcs.gla.ac.uk/publications/PAPERS/6769/TR-2002-123.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.7BBEB618 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |