Abstract
We consider the problem of computing a large stable matching in a bipartite graph G = (A ∪ B, E) where each vertex u ∈ A ∪ B ranks its neighbors in an order of preference, perhaps involving ties. A matching M is said to be stable if there is no edge (a,b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that computing a maximum size stable matching is APX-hard.
In this paper we consider the case when the preference lists of vertices in A are strict while the preference lists of vertices in B may include ties. This case is also APX-hard and the current best approximation ratio known here is 25/17 ≈ 1.4706 which relies on solving an LP. We improve this ratio to 22/15 ≈ 1.4667 by a simple linear time algorithm.
We first compute a half-integral stable matching in {0,0.5,1}|E| and round it to an integral stable matching M. The ratio |OPT|/|M| is bounded via a payment scheme that charges other components in OPT ⊕ M to cover the costs of length-5 augmenting paths. There will be no length-3 augmenting paths here.
We also consider the following special case of two-sided ties, where every tie length is 2. This case is known to be UGC-hard to approximate to within 4/3. We show a 10/7 ≈ 1.4286 approximation algorithm here that runs in linear time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Askalidis, G., Immorlica, N., Kwanashie, A., Manlove, D.F., Pountourakis, E.: Socially stable matchings in the hospitals / residents problem. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 85–96. Springer, Heidelberg (2013)
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. American Math. Monthly 69, 9–15 (1962)
Gale, D., Sotomayer, M.: Some remarks on the stable marriage problem. Discrete Applied Mathematics 11, 223–232 (1985)
Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Boston (1989)
Halldórsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Randomized approximation of the stable marriage problem. Theoretical Computer Science 325(3), 439–465 (2004)
Irving, R.W.: Stable marriage and indifference. Discrete Applied Mathematics 48, 261–272 (1994)
Irving, R.W., Manlove, D.F.: Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems. Journal of Combinatorial Optimization 16(3), 279–292 (2008)
Iwama, K., Manlove, D.F., Miyazaki, S., Morita, Y.: Stable marriage with incomplete lists and ties. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 443–452. Springer, Heidelberg (1999)
Iwama, K., Miyazaki, S., Yamauchi, N.: A 1.875-approximation algorithm for the stable marriage problem. In: 18th SODA, pp. 288–297 (2007)
Iwama, K., Miyazaki, S., Yanagisawa, H.: A 25/17-approximation algorithm for the stable marriage problem with one-sided ties. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 135–146. Springer, Heidelberg (2010)
Király, Z.: Better and simpler approximation algorithms for the stable marriage problem. Algorithmica 60(1), 3–20 (2011)
Király, Z.: Linear time local approximation algorithm for maximum stable marriage. Algorithms 6(3), 471–484 (2013)
Knuth, D.: Mariages stables et leurs relations avec d’autre problèmes. Les Presses de l’université de Montréal (1976)
Manlove, D.: Algorithmics of Matching Under Preferences. World Scientific Publishing Company Incorporated (2013)
Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theoretical Computer Science 276(1-2), 261–279 (2002)
McDermid, E.: A 3/2 approximation algorithm for general stable marriage. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 689–700. Springer, Heidelberg (2009)
Paluch, K.: Faster and simpler approximation of stable matchings. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol. 7164, pp. 176–187. Springer, Heidelberg (2012)
Roth, A., Sotomayor, M.: Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press (1992)
Teo, C.-P., Sethuraman, J., Tan, W.P.: Gale-Shapley stable marriage problem revisited: strategic issues and applications. In: Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 429–438. Springer, Heidelberg (1999)
Vande Vate, J.: Linear Programming brings marital bliss. Operation Research Letters 8, 147–153 (1989)
Yanagisawa, H.: Approximation algorithms for stable marriage problems. Ph.D. Thesis, Kyoto University (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Huang, CC., Kavitha, T. (2014). An Improved Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties. In: Lee, J., Vygen, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2014. Lecture Notes in Computer Science, vol 8494. Springer, Cham. https://doi.org/10.1007/978-3-319-07557-0_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-07557-0_25
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07556-3
Online ISBN: 978-3-319-07557-0
eBook Packages: Computer ScienceComputer Science (R0)