تقرير
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 |
الوصف غير متاح. |