Academic Journal
UK Finding Large Stable Matchings∗
| العنوان: | UK Finding Large Stable Matchings∗ |
|---|---|
| المؤلفون: | Robert W. Irving, David F. Manlove |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://www.dcs.gla.ac.uk/publications/PAPERS/8989/HRT_heuristic_techrep.pdf. |
| سنة النشر: | 2008 |
| المجموعة: | CiteSeerX |
| الوصف: | When ties and incomplete preference lists are permitted in the Stable Marriage and Hospitals/Residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we present two new heuristics for finding large stable matchings in variants of these problems in which ties are on one side only. We describe an empirical study involving these heuristics and the best existing approximation algorithm in such problem contexts. Our results indicate that one of these new heuristics has the best performance of the three algorithms, when applied to real-world and randomly-generated data sets. This study, and these particular problem variants, are motivated by important applications in large scale centralized matching schemes. 1 |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.621.6712; http://www.dcs.gla.ac.uk/publications/PAPERS/8989/HRT_heuristic_techrep.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.621.6712 http://www.dcs.gla.ac.uk/publications/PAPERS/8989/HRT_heuristic_techrep.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.E2D93AD9 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |