×

Maximum stable matching with one-sided ties of bounded length. (English) Zbl 1489.68401

Summary: We study the problem of finding maximum weakly stable matchings when preference lists are incomplete and contain one-sided ties of bounded length. We show that if the tie length is at most \(L\), then it is possible to achieve an approximation ratio of \(1+(1-\frac{1}{L})^L\). We also show that the same ratio is an upper bound on the integrality gap, which matches the known lower bound. In the case where the tie length is at most 2, our result implies an approximation ratio and integrality gap of \(\frac{5}{4}\), which matches the known UG-hardness result.

MSC:

68W25 Approximation algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B68 Matching models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lam, C-K, Plaxton, C.G.: A (1 + 1/e)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp 2823-2840 (2019) · Zbl 1432.68579
[2] Lam, C-K, Plaxton, C.G.: Maximum stable matching with one-sided ties of bounded length. In: Proceedings of the 12th International Symposium on Algorithmic Game Theory, pp 343-356 (2019) · Zbl 1431.91260
[3] Gale, D.; Shapley, LS, College admissions and the stability of marriage, Amer. Math. Monthly, 69, 1, 9-15 (1962) · Zbl 0109.24403 · doi:10.1080/00029890.1962.11989827
[4] Irving, RW, Stable marriage and indifference, Discret. Appl. Math., 48, 3, 261-272 (1994) · Zbl 0796.05078 · doi:10.1016/0166-218X(92)00179-P
[5] Gale, D.; Sotomayor, MAO, Some remarks on the stable matching problem, Discret. Appl. Math., 11, 3, 223-232 (1985) · Zbl 0596.90054 · doi:10.1016/0166-218X(85)90074-5
[6] Roth, AE, The evolution of the labor market for medical interns and residents: A case study in game theory, J. Polit. Econ., 92, 6, 991-1016 (1984) · doi:10.1086/261272
[7] Manlove, DF; Irving, RW; Iwama, K.; Miyazaki, S.; Morita, Y., Hard variants of stable marriage, Theor. Comput. Sci., 276, 1, 261-279 (2002) · Zbl 1050.68171 · doi:10.1016/S0304-3975(01)00206-7
[8] Iwama, K., Miyazaki, S., Yamauchi, N.: A 1.875-approximation algorithm for the stable marriage problem. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp 288-297 (2007) · Zbl 1302.68319
[9] Király, Z., Better and simpler approximation algorithms for the stable marriage problem, Algorithmica, 60, 1, 3-20 (2011) · Zbl 1216.68341 · doi:10.1007/s00453-009-9371-7
[10] McDermid, E.J.: A 3/2-approximation algorithm for general stable marriage. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp 689-700 (2009) · Zbl 1248.68564
[11] Paluch, K., Faster and simpler approximation of stable matchings, Algorithms, 7, 2, 189-202 (2014) · Zbl 1461.68259 · doi:10.3390/a7020189
[12] Király, Z., Linear time local approximation algorithm for maximum stable marriage, Algorithms, 6, 3, 471-484 (2013) · Zbl 1461.68257 · doi:10.3390/a6030471
[13] Iwama, K., Manlove, D.F., Miyazaki, S., Morita, Y.: Stable marriage with incomplete lists and ties. In: Proceedings of the 26th International Colloquium on Automata, Languages, and Programming, pp 443-452 (1999) · Zbl 0948.90155
[14] Halldórsson, MM; Irving, RW; Iwama, K.; Manlove, DF; Miyazaki, S.; Morita, Y.; Scott, S., Approximability results for stable marriage problems with ties, Theor. Comput. Sci., 306, 1, 431-447 (2003) · Zbl 1060.68085 · doi:10.1016/S0304-3975(03)00321-9
[15] Yanagisawa, H.: Approximation algorithms for stable marriage problems. Ph.D. Thesis, Graduate School of Informatics, Kyoto University (2007) · Zbl 1209.68643
[16] Iwama, K.; Miyazaki, S.; Yanagisawa, H., A 25/17-approximation algorithm for the stable marriage problem with one-sided ties, Algorithmica, 68, 3, 758-775 (2014) · Zbl 1360.68904 · doi:10.1007/s00453-012-9699-2
[17] Dean, B.C., Jalasutram, R.: Factor revealing LPs and stable matching with ties and incomplete lists. In: Proceedings of the 3rd International Workshop on Matching Under Preferences, pp 42-53 (2015)
[18] Huang, C-C; Kavitha, T., Improved approximation algorithms for two variants of the stable marriage problem with ties, Math. Program., 154, 1, 353-380 (2015) · Zbl 1411.91422 · doi:10.1007/s10107-015-0923-0
[19] Bauckholt, F., Pashkovich, K., Sanità, L.: On the approximability of the stable marriage problem with one-sided ties. arXiv:1805.05391(2018)
[20] Radnai, A.: Approximation algorithms for the stable marriage problem. Master’s Thesis, Department of Computer Science, Eötvös Loránd University (2014)
[21] Halldórsson, MM; Iwama, K.; Miyazaki, S.; Yanagisawa, H., Improved approximation results for the stable marriage problem, ACM Trans. Algorithm., 3, 3, 30 (2007) · Zbl 1192.68903 · doi:10.1145/1273340.1273346
[22] Huang, C-C, Iwama, K., Miyazaki, S., Yanagisawa, H.: A tight approximation bound for the stable marriage problem with restricted ties. In: Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp 361-380 (2015) · Zbl 1375.68219
[23] Halldórsson, MM; Iwama, K.; Miyazaki, S.; Yanagisawa, H., Randomized approximation of the stable marriage problem, Theor. Comput. Sci., 325, 3, 439-465 (2004) · Zbl 1071.68080 · doi:10.1016/j.tcs.2004.02.045
[24] Chiang, R., Pashkovich, K.: On the approximability of the stable matching problem with ties of size two. arXiv:1808.04510 (2019) · Zbl 1453.68212
[25] Irving, RW; Manlove, DF; O’Malley, G., Stable marriage with ties and bounded length preference lists, J. Discret. Algorithm., 7, 2, 213-219 (2009) · Zbl 1187.68346 · doi:10.1016/j.jda.2008.09.003
[26] Abraham, D.J., Levavi, A., Manlove, D.F., O’Malley, G.: The stable roommates problem with globally-ranked pairs. In: Proceedings of the 3rd International Workshop on Web and Internet Economics, pp 431-444 (2007)
[27] Irving, RW; Manlove, DF; Scott, S., The stable marriage problem with master preference lists, Discret. Appl. Math., 156, 15, 2959-2977 (2008) · Zbl 1175.05111 · doi:10.1016/j.dam.2008.01.002
[28] Marx, D.; Schlotter, I., Parameterized complexity and local search approaches for the stable marriage problem with ties, Algorithmica, 58, 1, 170-187 (2010) · Zbl 1204.68148 · doi:10.1007/s00453-009-9326-z
[29] Hamada, K., Miyazaki, S., Yanagisawa, H.: Strategy-proof approximation algorithms for the stable marriage problem with ties and incomplete lists. In: Proceedings of the 30th International Symposium on Algorithms and Computation, pp 9:1-9:14 (2019) · Zbl 07650242
[30] Jain, K.; Mahdian, M.; Markakis, E.; Saberi, A.; Vazirani, V., Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM, 50, 6, 795-824 (2003) · Zbl 1325.90060 · doi:10.1145/950620.950621
[31] Fernandes, CG; Meira, LAA; Miyazawa, FK; Pedrosa, LLC, A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems, Math. Program., 153, 2, 655-685 (2015) · Zbl 1369.90143 · doi:10.1007/s10107-014-0821-x
[32] Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp 597-606 (2011) · Zbl 1288.68288
[33] Mehta, A.; Saberi, A.; Vazirani, U.; Vazirani, V., Adwords and generalized online matching, J. ACM, 54, 5, 22:1-22:19 (2007) · Zbl 1312.68239 · doi:10.1145/1284320.1284321
[34] Rothblum, UG, Characterization of stable matchings as extreme points of a polytope, Math. Program., 54, 1, 57-67 (1992) · Zbl 0773.90059 · doi:10.1007/BF01586041
[35] Vande Vate, JH, Linear programming brings marital bliss, Oper. Res. Lett., 8, 3, 147-153 (1989) · Zbl 0675.90058 · doi:10.1016/0167-6377(89)90041-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.