{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T13:21:32Z","timestamp":1775654492694,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T00:00:00Z","timestamp":1775606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T00:00:00Z","timestamp":1775606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2047\/1 \u2013 390685813,MN 59\/4-1"],"award-info":[{"award-number":["EXC-2047\/1 \u2013 390685813,MN 59\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study the Euclidean minimum weight perfect matching problem for\n                    <jats:italic>n<\/jats:italic>\n                    points in the plane. It is known that any deterministic approximation algorithm whose approximation ratio depends only on\n                    <jats:italic>n<\/jats:italic>\n                    requires at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\Omega (n \\log n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03a9<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time. We propose such an algorithm for the Euclidean minimum weight perfect matching problem with runtime\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n\\log n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and show that it has approximation ratio\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n^{0.206})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mn>0.206<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . This improves the so far best known approximation ratio of\n                    <jats:italic>n<\/jats:italic>\n                    \/2. We also develop an\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n \\log n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    algorithm for the Euclidean minimum weight perfect matching problem in higher dimensions and show it has approximation ratio\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n^{0.412})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mn>0.412<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    in all fixed dimensions.\n                  <\/jats:p>","DOI":"10.1007\/s00224-025-10254-7","type":"journal-article","created":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T12:35:12Z","timestamp":1775651712000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8656-3418","authenticated-orcid":false,"given":"Stefan","family":"Hougardy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karolina","family":"Tammemaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,8]]},"reference":[{"issue":"5","key":"10254_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998). https:\/\/doi.org\/10.1145\/290179.290180","journal-title":"J. ACM"},{"key":"10254_CR2","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/PL00009340","volume":"6","author":"SN Bespamyatnikh","year":"1998","unstructured":"Bespamyatnikh, S.N.: An optimal algorithm for closest-pair maintenance. Discrete Comput. Geom. 6, 175\u2013195 (1998). https:\/\/doi.org\/10.1007\/PL00009340","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"10254_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. B 69B(1), 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand. B"},{"key":"10254_CR4","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). https:\/\/doi.org\/10.4153\/CJM-1965-045-4","journal-title":"Can. J. Math."},{"key":"10254_CR5","unstructured":"Gabow, H.: An efficient implementation of Edmonds\u2019 maximum matching algorithm. Technical report no. 31, Digital Systems Laboratory, Stanford University, (1972)"},{"key":"10254_CR6","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(86)90143-2","volume":"22","author":"MD Grigoriadis","year":"1986","unstructured":"Grigoriadis, M.D., Kalantari, B.: A lower bound to the complexity of Euclidean and rectilinear matching algorithms. Inf. Process. Lett. 22, 73\u201376 (1986). https:\/\/doi.org\/10.1016\/0020-0190(86)90143-2","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10254_CR7","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/BF01442866","volume":"6","author":"C Hierholzer","year":"1873","unstructured":"Hierholzer, C.: Ueber die M\u00f6glichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Math. Ann. 6(1), 30\u201332 (1873). https:\/\/doi.org\/10.1007\/BF01442866","journal-title":"Math. Ann."},{"key":"10254_CR8","doi-asserted-by":"publisher","unstructured":"Hougardy, S., Tammemaa, K.: Fast approximation algorithms for Euclidean minimum weight perfect matching. In: Bie\u0144kowski, M., Englert, M. (eds.) Approximation and Online Algorithms. WAOA 2024, volume 15269 of Lecture Notes in Computer Science, pp. 76\u201388 (2025). https:\/\/doi.org\/10.1007\/978-3-031-81396-2_6","DOI":"10.1007\/978-3-031-81396-2_6"},{"key":"10254_CR9","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York (1976)"},{"key":"10254_CR10","doi-asserted-by":"publisher","unstructured":"Preparata, F.P., Shamos, M.I.: Computational geometry. An introduction. Texts and monographs in computer science. Springer Verlag, (1985). https:\/\/doi.org\/10.1007\/978-1-4612-1098-6","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"10254_CR11","doi-asserted-by":"publisher","unstructured":"Rao, S.B., Smith, W.D.: Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 540\u2013550, (1998). https:\/\/doi.org\/10.1145\/276698.276868","DOI":"10.1145\/276698.276868"},{"key":"10254_CR12","doi-asserted-by":"crossref","unstructured":"Rao, S.B., Smith, W.D.: Improved approximation schemes for geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d. unpublished extended version of\u00a0[10], (1998). https:\/\/rangevoting.org\/WarrenSmithPages\/homepage\/rao-smith-tsp.ps","DOI":"10.1145\/276698.276868"},{"issue":"4","key":"10254_CR13","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0210050","volume":"10","author":"EM Reingold","year":"1981","unstructured":"Reingold, E.M., Tarjan, R.E.: On a greedy heuristic for complete matching. SIAM J. Comput. 10(4), 676\u2013681 (1981). https:\/\/doi.org\/10.1137\/0210050","journal-title":"SIAM J. Comput."},{"key":"10254_CR14","doi-asserted-by":"publisher","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In: 16th Annual Symposium on Foundations of Computer Science (FOCS 1975), pp. 151\u2013162. IEEE, (1975). https:\/\/doi.org\/10.1109\/SFCS.1975.8","DOI":"10.1109\/SFCS.1975.8"},{"key":"10254_CR15","doi-asserted-by":"publisher","unstructured":"Supowit, K.J., Plaisted, D.A., Reingold, E.M.: Heuristics for weighted perfect matching. In: STOC \u201980: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 398\u2013419 (1980). https:\/\/doi.org\/10.1145\/800141.804689","DOI":"10.1145\/800141.804689"},{"key":"10254_CR16","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/BF01553909","volume":"4","author":"PM Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Approximate minimum weight matching on points in $$k$$-dimensional space. Algorithmica 4, 569\u2013583 (1989). https:\/\/doi.org\/10.1007\/BF01553909","journal-title":"Algorithmica"},{"issue":"6","key":"10254_CR17","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"PM Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Geometry helps in matching. SIAM J. Comput. 18(6), 1201\u20131225 (1989). https:\/\/doi.org\/10.1137\/0218080","journal-title":"SIAM J. Comput."},{"key":"10254_CR18","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"PM Vaidya","year":"1989","unstructured":"Vaidya, P.M.: An $${O} (n \\log n)$$ algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom. 4, 101\u2013115 (1989). https:\/\/doi.org\/10.1007\/BF02187718","journal-title":"Discrete Comput. Geom."},{"key":"10254_CR19","doi-asserted-by":"publisher","unstructured":"Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: Proceedings 39th Annual Symposium on Foundations of Computer Science, pp. 320\u2013329. IEEE, (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743466","DOI":"10.1109\/SFCS.1998.743466"},{"key":"10254_CR20","unstructured":"Varadarajan, K.R., Agarwal, P.K.: Approximation algorithms for bipartite and non-bipartite matching in the plane. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201999, pp. 805\u2013814 (1999)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10254-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10254-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10254-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T12:35:15Z","timestamp":1775651715000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10254-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,8]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10254"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10254-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,8]]},"assertion":[{"value":"31 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"25"}}