تقرير
On the approximability of the stable matching problem with ties of size two
| العنوان: | On the approximability of the stable matching problem with ties of size two |
|---|---|
| المؤلفون: | Chiang, Robert, Pashkovich, Kanstantsin |
| سنة النشر: | 2018 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory, Mathematics - Optimization and Control |
| الوصف: | The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3. In this paper, we give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor. Comment: Added a detailed comparison with the approaches from the papers "On the approximability of the stable marriage problem with one-sided ties." by Bauckholt, Pashkovich, and Sanita and "Improved approximation algorithms for two variants of the stable marriage problem with ties." by Huang and Kavitha. (See Appendix) |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1808.04510 |
| رقم الأكسشن: | edsarx.1808.04510 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |