{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:11:15Z","timestamp":1761401475808},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,8,22]],"date-time":"2009-08-22T00:00:00Z","timestamp":1250899200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1007\/s00453-009-9353-9","type":"journal-article","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T13:54:10Z","timestamp":1250862850000},"page":"102-118","source":"Crossref","is-referenced-by-count":29,"title":["Almost Stable Matchings by Truncating the\u00a0Gale\u2013Shapley Algorithm"],"prefix":"10.1007","volume":"58","author":[{"given":"Patrik","family":"Flor\u00e9en","sequence":"first","affiliation":[]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[]},{"given":"Valentin","family":"Polishchuk","sequence":"additional","affiliation":[]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,22]]},"reference":[{"key":"9353_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/11774129","volume-title":"Proc. of the 3rd Workshop on Approximation and Online Algorithms (WAOA)","author":"D.J. Abraham","year":"2006","unstructured":"Abraham, D.J., Bir\u00f3, P., Manlove, D.F.: \u201cAlmost stable\u201d matchings in the roommates problem. In: Proc. of the 3rd Workshop on Approximation and Online Algorithms (WAOA), Palma de Mallorca, Spain, October 2005. Lecture Notes in Computer Science, vol. 3879, pp. 1\u201314. Springer, Berlin (2006)"},{"key":"9353_CR2","first-page":"82","volume-title":"Proc. of the 12th Annual ACM Symposium on Theory of Computing (STOC)","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proc. of the 12th Annual ACM Symposium on Theory of Computing (STOC), Los Angeles, CA, USA, April 1980, pp. 82\u201393. ACM Press, New York (1980)"},{"issue":"4","key":"9353_CR3","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1002\/net.3230130404","volume":"13","author":"D. Avis","year":"1983","unstructured":"Avis, D.: A survey of heuristics for the weighted matching problem. Networks 13(4), 475\u2013493 (1983)","journal-title":"Networks"},{"key":"9353_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-540-93980-1_2","volume-title":"Proc. of the 6th Workshop on Approximation and Online Algorithms (WAOA)","author":"P. Bir\u00f3","year":"2009","unstructured":"Bir\u00f3, P., Manlove, D.F., Mittal, S.: Size versus stability in the marriage problem. In: Proc. of the 6th Workshop on Approximation and Online Algorithms (WAOA), Karlsruhe, Germany, September 2008. Lecture Notes in Computer Science, vol. 5426, pp. 15\u201328. Springer, Berlin (2009)"},{"key":"9353_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-540-87779-0_6","volume-title":"Proc. of the 22nd International Symposium on Distributed Computing (DISC)","author":"A. Czygrinow","year":"2008","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proc. of the 22nd International Symposium on Distributed Computing (DISC), Arcachon, France, September 2008. Lecture Notes in Computer Science, vol. 5218, pp. 78\u201392. Springer, Berlin (2008)"},{"issue":"3\u20134","key":"9353_CR6","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00182-007-0081-6","volume":"36","author":"K. Eriksson","year":"2008","unstructured":"Eriksson, K., H\u00e4ggstr\u00f6m, O.: Instability of matchings in decentralized markets with various preference structures. Int. J. Game Theory 36(3\u20134), 409\u2013420 (2008)","journal-title":"Int. J. Game Theory"},{"issue":"1\u20132","key":"9353_CR7","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/S0304-3975(99)00125-5","volume":"233","author":"T. Feder","year":"2000","unstructured":"Feder, T., Megiddo, N., Plotkin, S.A.: A sublinear parallel algorithm for stable matching. Theor. Comput. Sci. 233(1\u20132), 297\u2013308 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9353_CR8","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1287\/moor.28.1.103.14256","volume":"28","author":"T. Fleiner","year":"2003","unstructured":"Fleiner, T.: A fixed-point approach to stable matchings and some applications. Math. Oper. Res. 28(1), 103\u2013126 (2003)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9353_CR9","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D. Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"9353_CR10","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D. Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)"},{"key":"9353_CR11","unstructured":"Halld\u00f3rsson, M.M., Irving, R.W., Iwama, K., Manlove, D.F. (eds): MATCH-UP: matching under preferences\u2014algorithms and complexity. Satellite workshop of ICALP 2008, July 2008"},{"key":"9353_CR12","first-page":"219","volume-title":"Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Ha\u0144\u0107kowiak","year":"1998","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. In: Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, USA, January 1998, pp. 219\u2013225. Society for Industrial and Applied Mathematics, Philadelphia (1998)"},{"key":"9353_CR13","unstructured":"Hassinen, M., Kaasinen, J., Kranakis, E., Polishchuk, V., Suomela, J., Wiese, A.: Analysing local algorithms in location-aware quasi unit-disk graphs (2009, submitted for publication)"},{"key":"9353_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/11780823_10","volume-title":"Proc. of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"J.-H. Hoepman","year":"2006","unstructured":"Hoepman, J.-H., Kutten, S., Lotker, Z.: Efficient distributed weighted matchings on trees. In: Proc. of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Chester, UK, July 2006. Lecture Notes in Computer Science, vol. 4056, pp. 115\u2013129. Springer, Berlin (2006)"},{"issue":"2","key":"9353_CR15","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0020-0190(84)90025-5","volume":"18","author":"M.E.C. Hull","year":"1984","unstructured":"Hull, M.E.C.: A parallel view of stable marriages. Inf. Process. Lett. 18(2), 63\u201366 (1984)","journal-title":"Inf. Process. Lett."},{"key":"9353_CR16","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Rucinski, A.: Random Graphs. Wiley, New York (2000)"},{"issue":"2","key":"9353_CR17","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9353_CR18","first-page":"466","volume-title":"Proc. of the 29th IEEE International Conference on Distributed Computing Systems (ICDCS)","author":"A. Kipnis","year":"2009","unstructured":"Kipnis, A., Patt-Shamir, B.: A note on distributed stable matching. In: Proc. of the 29th IEEE International Conference on Distributed Computing Systems (ICDCS), pp.\u00a0466\u2013473. Montreal, QC, Canada, June 2009. IEEE Computer Society, Los Alamitos (2009)"},{"key":"9353_CR19","volume-title":"Mariages Stables","author":"D.E. Knuth","year":"1976","unstructured":"Knuth, D.E.: Mariages Stables. Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al, Montr\u00e9al (1976)"},{"key":"9353_CR20","unstructured":"Kuhn, F.: The price of locality: exploring the complexity of distributed coordination primitives. Ph.D. thesis, ETH Z\u00fcrich (2005)"},{"key":"9353_CR21","first-page":"980","volume-title":"Proc. of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"F. Kuhn","year":"2006","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, FL, USA, January 2006, pp. 980\u2013989. ACM, New York (2006)"},{"issue":"1","key":"9353_CR22","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"9353_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-3-540-24596-4_7","volume-title":"Proc. of the 10th International Conference on High Performance Computing (HiPC)","author":"E. Lu","year":"2003","unstructured":"Lu, E., Zheng, S.Q.: A parallel iterative improvement stable matching algorithm. In: Proc. of the 10th International Conference on High Performance Computing (HiPC), Hyderabad, India, December 2003. Lecture Notes in Computer Science, vol. 2913, pp. 55\u201365. Springer, Berlin (2003)"},{"key":"9353_CR24","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1109\/ISTCS.1995.377023","volume-title":"Proc. of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS)","author":"A. Mayer","year":"1995","unstructured":"Mayer, A., Naor, M., Stockmeyer, L.: Local computations on static and dynamic graphs. In: Proc. of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS), Tel Aviv, Israel, January 1995, pp. 268\u2013278. IEEE, Piscataway (1995)"},{"key":"9353_CR25","unstructured":"Moscibroda, T.: Locality, scheduling, and selfishness: algorithmic foundations of highly decentralized networks. Ph.D. thesis, ETH Z\u00fcrich (2006)"},{"issue":"6","key":"9353_CR26","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M. Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"9353_CR27","first-page":"327","volume-title":"Proc. of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"H.N. Nguyen","year":"2008","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proc. of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, PA, USA, October 2008, pp. 327\u2013336. IEEE Computer Society, Los Alamitos (2008)"},{"issue":"1\u20133","key":"9353_CR28","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","volume":"381","author":"M. Parnas","year":"2007","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci. 381(1\u20133), 183\u2013196 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9353_CR29","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/BF01935367","volume":"25","author":"M.J. Quinn","year":"1985","unstructured":"Quinn, M.J.: A note on two parallel algorithms to solve the stable marriage problem. BIT Numer. Math. 25(3), 473\u2013476 (1985)","journal-title":"BIT Numer. Math."},{"issue":"6","key":"9353_CR30","doi-asserted-by":"crossref","first-page":"1475","DOI":"10.2307\/2938326","volume":"58","author":"A.E. Roth","year":"1990","unstructured":"Roth, A.E., Vande Vate, J.H.: Random paths to stability in two-sided matching. Econometrica 58(6), 1475\u20131480 (1990)","journal-title":"Econometrica"},{"key":"9353_CR31","unstructured":"Suomela, J.: Survey of local algorithms. http:\/\/www.iki.fi\/jukka.suomela\/local-survey (2009, submitted for publication)"},{"issue":"3","key":"9353_CR32","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/BF02219230","volume":"29","author":"S.S. Tseng","year":"1989","unstructured":"Tseng, S.S.: The average performance of a parallel stable marriage algorithm. BIT Numer. Math. 29(3), 448\u2013456 (1989)","journal-title":"BIT Numer. Math."},{"issue":"3","key":"9353_CR33","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1007\/BF02136029","volume":"24","author":"S.S. Tseng","year":"1984","unstructured":"Tseng, S.S., Lee, R.C.T.: A parallel algorithm to solve the stable marriage problem. BIT Numer. Math. 24(3), 308\u2013316 (1984)","journal-title":"BIT Numer. Math."},{"key":"9353_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/978-3-540-30186-8_24","volume-title":"Proc. of the 18th International Symposium on Distributed Computing (DISC)","author":"M. Wattenhofer","year":"2004","unstructured":"Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: Proc. of the 18th International Symposium on Distributed Computing (DISC), Amsterdam, The Netherlands, October 2004. Lecture Notes in Computer Science, vol. 3274, pp. 335\u2013348. Springer, Berlin (2004)"},{"key":"9353_CR35","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Proc. of the 7th International Conference on Ad-Hoc Networks & Wireless (AdHoc-NOW)","author":"A. Wiese","year":"2008","unstructured":"Wiese, A., Kranakis, E.: Local maximal matching and local 2-approximation for vertex cover in UDGs. In: Proc. of the 7th International Conference on Ad-Hoc Networks & Wireless (AdHoc-NOW), Sophia Antipolis, France, September 2008. Lecture Notes in Computer Science, vol. 5198, pp. 1\u201314. Springer, Berlin (2008)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9353-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9353-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9353-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:04Z","timestamp":1559137504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9353-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,22]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["9353"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9353-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,22]]}}}