{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T16:13:41Z","timestamp":1767888821870,"version":"3.49.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,18]],"date-time":"2015-09-18T00:00:00Z","timestamp":1442534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,9,18]],"date-time":"2015-09-18T00:00:00Z","timestamp":1442534400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SCHN 503\/6-1"],"award-info":[{"award-number":["SCHN 503\/6-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","award":["Supported within the Feodor Lynen program"],"award-info":[{"award-number":["Supported within the Feodor Lynen program"]}],"id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1115256"],"award-info":[{"award-number":["CCF-1115256"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00453-015-0062-2","type":"journal-article","created":{"date-parts":[[2015,9,18]],"date-time":"2015-09-18T13:59:51Z","timestamp":1442584791000},"page":"201-234","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Greedy Matching: Guarantees and Limitations"],"prefix":"10.1007","volume":"77","author":[{"given":"Bert","family":"Besser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Poloczek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,18]]},"reference":[{"issue":"26\u201328","key":"62_CR1","doi-asserted-by":"publisher","first-page":"2542","DOI":"10.1016\/j.tcs.2010.03.014","volume":"411","author":"S Angelopoulos","year":"2010","unstructured":"Angelopoulos, S., Borodin, A.: Randomized priority algorithms. Theor. Comput. Sci. 411(26\u201328), 2542\u20132558 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"62_CR2","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/rsa.3240060107","volume":"6","author":"J Aronson","year":"1995","unstructured":"Aronson, J., Dyer, M.E., Frieze, A.M., Suen, S.: Randomized greedy matching II. Random Struct. Algorithms 6(1), 55\u201374 (1995)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"62_CR3","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#","volume":"12","author":"J Aronson","year":"1998","unstructured":"Aronson, J., Frieze, A.M., Pittel, B.: Maximum matchings in sparse random graphs: Karp\u2013Sipser revisited. Random Struct. Algorithms 12(2), 111\u2013177 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"62_CR4","unstructured":"Bennett, P., Bohman, T.: A Natural Barrier in Random Greedy Hypergraph Matching. CoRR (2012). arXiv:1210.3581"},{"key":"62_CR5","unstructured":"Berger, B., Singh, R., Xu, J.: Graph algorithms for biological systems analysis. In: Proceedings of the Nineteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 142\u2013151 (2008)"},{"key":"62_CR6","unstructured":"Besser, B., Werth, B.: On the Approximation Performance of Degree Heuristics for Matching. CoRR (2015). arXiv:1504.05830"},{"issue":"1","key":"62_CR7","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.tcs.2009.09.033","volume":"411","author":"A Borodin","year":"2010","unstructured":"Borodin, A., Boyar, J., Larsen, K.S., Mirmohammadi, N.: Priority algorithms for graph optimization problems. Theor. Comput. Sci. 411(1), 239\u2013258 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"62_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2011.11.010","volume":"418","author":"A Borodin","year":"2012","unstructured":"Borodin, A., Ivan, I., Ye, Y., Zimny, B.: On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418, 1\u201313 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"62_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A Borodin","year":"2003","unstructured":"Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica 37(4), 295\u2013326 (2003)","journal-title":"Algorithmica"},{"key":"62_CR10","doi-asserted-by":"crossref","unstructured":"Chan, T.H.H., Chen, F., Wu, X., Zhao, Z.: Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints. In: Proceedings of the Twenty-Fifth Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 1112\u20131122 (2014)","DOI":"10.1137\/1.9781611973402.82"},{"issue":"1\u20132","key":"62_CR11","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s10107-011-0451-5","volume":"135","author":"Y Chan","year":"2012","unstructured":"Chan, Y., Lau, L.: On linear and semidefinite programming relaxations for hypergraph matching. Math. Program. 135(1\u20132), 123\u2013148 (2012)","journal-title":"Math. Program."},{"key":"62_CR12","doi-asserted-by":"crossref","unstructured":"Cheng, Y.Q., Wu, V., Collins, R.T., Hanson, A.R., Riseman, E.M.: Maximum-weight bipartite matching technique and its application in image feature matching. In: Proceedings of the SPIE Visual Communications and Image Processing (1996)","DOI":"10.1117\/12.233261"},{"key":"62_CR13","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 509\u2013518 (2013)","DOI":"10.1109\/FOCS.2013.61"},{"issue":"3","key":"62_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00453-007-9124-4","volume":"54","author":"S Davis","year":"2009","unstructured":"Davis, S., Impagliazzo, R.: Models of greedy algorithms for graph problems. Algorithmica 54(3), 269\u2013317 (2009)","journal-title":"Algorithmica"},{"key":"62_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"issue":"1","key":"62_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/rsa.3240020104","volume":"2","author":"ME Dyer","year":"1991","unstructured":"Dyer, M.E., Frieze, A.M.: Randomized greedy matching. Random Struct. Algorithms 2(1), 29\u201346 (1991)","journal-title":"Random Struct. Algorithms"},{"key":"62_CR17","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"62_CR18","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Fulkerson, D.R.: Transversals and matroid partition. J. Res. Natl. Bur. Stand 69B(3), 147\u2013153 (1965)","DOI":"10.6028\/jres.069B.016"},{"key":"62_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1017\/S0963548300001474","volume":"4","author":"AM Frieze","year":"1995","unstructured":"Frieze, A.M., Radcliffe, A.J., Suen, S.: Analysis of a simple greedy matching algorithm on random cubic graphs. Comb. Probab. Comput. 4, 47\u201366 (1995)","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"62_CR20","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"HN Gabow","year":"1976","unstructured":"Gabow, H.N.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. J. ACM 23(2), 221\u2013234 (1976)","journal-title":"J. ACM"},{"key":"62_CR21","unstructured":"Gabow, H.N.: Set-Merging for the Matching Algorithm of Micali and Vazirani. CoRR (2014). arXiv:1501.00212"},{"issue":"1","key":"62_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s004930070031","volume":"20","author":"JF Geelen","year":"2000","unstructured":"Geelen, J.F.: An algebraic matching algorithm. Combinatorica 20(1), 61\u201370 (2000)","journal-title":"Combinatorica"},{"key":"62_CR23","doi-asserted-by":"crossref","unstructured":"Goel, G., Tripathi, P.: Matching with our eyes closed. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 718\u2013727 (2012)","DOI":"10.1109\/FOCS.2012.19"},{"issue":"3","key":"62_CR24","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10107-004-0505-z","volume":"100","author":"AV Goldberg","year":"2004","unstructured":"Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows and matchings. Math. Program. 100(3), 537\u2013568 (2004)","journal-title":"Math. Program."},{"issue":"2","key":"62_CR25","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1137\/070684008","volume":"39","author":"NJA Harvey","year":"2009","unstructured":"Harvey, N.J.A.: Algebraic algorithms for matching and matroid problems. SIAM J. Comput. 39(2), 679\u2013702 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"62_CR26","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20\u201339 (2006)","journal-title":"Comput. Complex."},{"issue":"1\u20132","key":"62_CR27","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s11235-006-9024-y","volume":"34","author":"M Hosaagrahara","year":"2007","unstructured":"Hosaagrahara, M., Sethu, H.: Degree-sequenced matching algorithms for input-queued switches. Telecommun. Syst. 34(1\u20132), 37\u201349 (2007)","journal-title":"Telecommun. Syst."},{"key":"62_CR28","doi-asserted-by":"crossref","unstructured":"Hougardy, S.: Linear time approximation algorithms for degree constrained subgraph problems. In: Cook, W., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 185\u2013200 (2009)","DOI":"10.1007\/978-3-540-76796-1_9"},{"key":"62_CR29","doi-asserted-by":"crossref","unstructured":"Huang, N., Borodin, A.: Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization. In: Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), pp. 528\u2013539 (2014)","DOI":"10.1007\/978-3-319-13075-0_42"},{"issue":"1","key":"62_CR30","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"CAJ Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"62_CR31","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 587\u2013596 (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"62_CR32","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Sipser, M.: Maximum matchings in sparse random graphs. In: Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013375 (1981)","DOI":"10.1109\/SFCS.1981.21"},{"key":"62_CR33","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"62_CR34","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B Korte","year":"1978","unstructured":"Korte, B., Hausmann, D.: An analysis of the greedy algorithm for independence systems. Ann. Discrete Math. 2, 65\u201374 (1978)","journal-title":"Ann. Discrete Math."},{"key":"62_CR35","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland, Amsterdam (1986)"},{"key":"62_CR36","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/297096.297131","volume":"3","author":"J Magun","year":"1998","unstructured":"Magun, J.: Greedy matching algorithms: an experimental study. ACM J. Exp. Algorithmics 3, 6 (1998)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"62_CR37","doi-asserted-by":"crossref","unstructured":"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 (STOC), pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"issue":"3","key":"62_CR38","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<353::AID-RSA5>3.0.CO;2-V","volume":"10","author":"Z Miller","year":"1997","unstructured":"Miller, Z., Pritikin, D.: On randomized greedy matchings. Random Struct. Algorithms 10(3), 353\u2013383 (1997)","journal-title":"Random Struct. Algorithms"},{"key":"62_CR39","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"62_CR40","doi-asserted-by":"crossref","unstructured":"Poloczek, M.: Bounds on greedy algorithms for MAX\u00a0SAT. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 37\u201348 (2011)","DOI":"10.1007\/978-3-642-23719-5_4"},{"key":"62_CR41","doi-asserted-by":"crossref","unstructured":"Poloczek, M., Szegedy, M.: Randomized greedy algorithms for the maximum matching problem with new analysis. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 708\u2013717 (2012)","DOI":"10.1109\/FOCS.2012.20"},{"issue":"2","key":"62_CR42","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.jet.2005.04.004","volume":"125","author":"AE Roth","year":"2005","unstructured":"Roth, A.E., S\u00f6nmez, T., \u00dcnver, M.U.: Pairwise kidney exchange. J. Econ. Theory 125(2), 151\u2013188 (2005)","journal-title":"J. Econ. Theory"},{"key":"62_CR43","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF01874391","volume":"1","author":"G Tinhofer","year":"1984","unstructured":"Tinhofer, G.: A probabilistic analysis of some greedy cardinality matching algorithms. Ann. Oper. Res. 1, 239\u2013254 (1984)","journal-title":"Ann. Oper. Res."},{"key":"62_CR44","unstructured":"Tripathi, P.: Allocation Problems with Partial Information. Ph.D. thesis, Georgia Institute of Technology (2012)"},{"key":"62_CR45","unstructured":"Vazirani, V.V.: A Simplification of the MV Matching Algorithm and Its Proof. CoRR (2013). arXiv:1210.4594"},{"key":"62_CR46","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Lower bounds by probabilistic arguments. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 420\u2013428. IEEE (1983)","DOI":"10.1109\/SFCS.1983.30"}],"updated-by":[{"DOI":"10.1007\/s00453-017-0281-9","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T00:00:00Z","timestamp":1489104000000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0062-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0062-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0062-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0062-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T18:14:05Z","timestamp":1748628845000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0062-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,18]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["62"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0062-2","relation":{"erratum":[{"id-type":"doi","id":"10.1007\/s00453-017-0281-9","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,18]]},"assertion":[{"value":"12 February 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}