{"entities":{"Q794175":{"pageid":796023,"ns":120,"title":"Item:Q794175","lastrevid":42698024,"modified":"2025-07-08T14:27:23Z","type":"item","id":"Q794175","labels":{"en":{"language":"en","value":"A partitioning algorithm for minimum weighted Euclidean matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3858438"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$851C2844-4E82-471B-9622-1FCB2CD0FBD5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4f6b28becf17542c86da1e8a93ab80bbaa8c72f6","datavalue":{"value":{"text":"A partitioning algorithm for minimum weighted Euclidean matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794175$39CCF98F-B493-4859-A460-3461A4E19334","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c60756eca9c34a22dd1572d37ff350ccfcd88e8","datavalue":{"value":"0539.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$F75388FC-19DC-41FF-9352-85595C6D9A19","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84c1dfe326344bde6bcfef739d485ec8b94399c4","datavalue":{"value":"10.1016/0020-0190(84)90024-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$366C6090-9F6F-43D3-BD86-C0F007B02AF6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$08471C87-A4F0-4137-B2EA-C528CF29C144","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q794175$960CD5B0-EEBC-47F8-A6B4-A7B9314027BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"510a43a4088d0522d7ed647f6e7560af29e0737a","datavalue":{"value":"In this paper an example is given of the following heuristics dealing with problems defined on random sets of points distributed uniformly in the Euclidean unit square in the plane: Partition the unit square in a number of smaller subsquares, each containing (on the average) only a small fraction of the points; solve each of these local subproblems, and try to combine these local solutions by some local patching into a global solution for the original instance of the problem. The analysis of the heuristics establishes in a well defined probabilistic model the probability of the event that the result of the heuristics is not much worse than the optimal solution. A classical example where this heuristics has been applied is \\textit{R. M. Karp's} application for the Euclidean traveling salesman problem [Math. Oper. Res. 2, 209-224 (1977; Zbl 0391.90091)]. In the present note the heuristics is applied to the problem of finding a minimal weighted Euclidean matching on a set of 2m points selected at random in the unit square. By dividing the square in \\(k^ 2\\) subsquares with \\(k=O(m^{1/2})\\) an algorithm is obtained approximating the optimal matching asymptotically with probability 1, such that its running time with high probability is \\(O(m^ 3/k^ 2)\\). The running time of an algorithm solving the problem exactly is \\(O(n^ 3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q794175$08E6E395-D79C-42CF-839F-C07D5FBC58DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$513FA2B8-A0E8-4AA5-9721-8C61711CABE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$6C71392B-953C-4B6A-8E76-6FF7D35615B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$CF5479AF-891D-4B8D-9EC0-FD87759E374D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4b01e6447a2d96fe20aba72cef22be0c4e9e97df","datavalue":{"value":"3858438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$7E70580C-BB75-44AB-B831-E20F3CD95D42","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6a700a002c6fe1fcd568fbdac44e45ecfeda53","datavalue":{"value":"probabilistic analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q794175$97D0412C-5AA9-4CAA-B0FA-A0985322EE67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4edeb3fb2452839fbb74eb9485a5af4ec0230650","datavalue":{"value":"minimal weighted Euclidean matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q794175$A38F913C-BF26-4E61-9503-335570B676A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ac6079b2082bbed271309fb2d51b5b4c5dd28d8","datavalue":{"value":{"entity-type":"item","numeric-id":247119,"id":"Q247119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$1CF56BE2-FD77-490D-B5BD-D7DB5CDA57C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$D4E767EB-4D4B-44B1-9B6F-FBE7160B8790","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ca9cd2a9131e1d8839142cee57f1e863d7371382","datavalue":{"value":{"entity-type":"item","numeric-id":582045,"id":"Q582045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$F95064DB-E6E0-4F55-8D44-99CA564F1C14","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$4536900A-37D4-4CFF-8DD8-0D68B40D802D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b08718589bc096df64aa7bbae63c50de9028822c","datavalue":{"value":"https://doi.org/10.1016/0020-0190(84)90024-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q794175$F1DB75BA-2E0C-427B-BF79-8E09781A7F64","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"477a3963ccec88324fedcf5b95c2f4be94acbbd5","datavalue":{"value":"W1991462609","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$CD069D99-85BC-47F2-936A-2453C0B7A8D3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"09d11e70e46a53068502fd8920c8774523c75dee","datavalue":{"value":"Q56324183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$A9D3C88B-1405-4390-9EF0-C9C0C27DD850","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"575c1ca78e17ba091b35694ba17530e4c427ffea","datavalue":{"value":{"entity-type":"item","numeric-id":1149255,"id":"Q1149255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$2156C739-DF3F-42BA-A428-F0194E335219","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$042F74B1-CD96-45E4-B958-F92A5DDFD508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$052B2944-C426-475D-8289-534CC99FDE9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9555240000c005c284f774f616cc245c303f7efd","datavalue":{"value":{"entity-type":"item","numeric-id":3937162,"id":"Q3937162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$9BB9B8E3-3EC3-409E-BBAB-6DDC1C2F66B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2105ff279dc4d548bf5fd676a1cf44ea440124ae","datavalue":{"value":{"entity-type":"item","numeric-id":4173216,"id":"Q4173216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$A2526EE9-10D6-4943-956C-9606687FA237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de047d2c791521fddc7ec2e80fbf90e0ef963378","datavalue":{"value":{"entity-type":"item","numeric-id":3969884,"id":"Q3969884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$34FA0ECC-F5E9-4D2D-BC2B-3EE74A0984AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a69a60844867c3ca63f6c08fb5c1f7735796c34","datavalue":{"value":{"entity-type":"item","numeric-id":3922185,"id":"Q3922185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$0E965EC8-EA65-4ECB-B88F-BA9AB54B79BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd9c902e18f256ef6ab9ecbbe60131e5487ac544","datavalue":{"value":{"entity-type":"item","numeric-id":1152627,"id":"Q1152627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$BCDE3B9B-23F8-438C-82B3-A308C6EC76A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62058d29248a0e715c2b29225723484ea23bbbb","datavalue":{"value":{"entity-type":"item","numeric-id":3967061,"id":"Q3967061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$84FD7342-6539-49C6-8964-038F989B1385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dc0559f16eedea55606af419809593245a47014","datavalue":{"value":{"entity-type":"item","numeric-id":3967062,"id":"Q3967062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794175$B7A9A453-323F-41D7-8795-C90B95D31421","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"d5020eee228c335f4cbfd01325feccb45bd30f31","datavalue":{"value":"journals/ipl/DyerF84","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794175$56560552-8127-4038-8935-089E8AB24186","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f545c1ee062a7917cc9d6e74ddfc61d56f3eabf9","datavalue":{"value":{"entity-type":"item","numeric-id":3202140,"id":"Q3202140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2191fce196f3d97ce6e2830e3208e9f5960e7b05","datavalue":{"value":{"amount":"+0.87093115","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$B350BEE3-2B16-4484-A1E2-42C863389465","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5222e8eafb69ca5907e92b734c3c77a3c10ca7c1","datavalue":{"value":{"entity-type":"item","numeric-id":4729617,"id":"Q4729617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c02f19742239a43c0cc8a36fd65474715b1f8b8b","datavalue":{"value":{"amount":"+0.8507913","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$744443B1-9780-435C-9001-65B940BE9B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c4dedd8dc8dc6da77a5a28d3b3cd0920ecc91eb","datavalue":{"value":{"entity-type":"item","numeric-id":800827,"id":"Q800827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c6aba0078a29b617be14281c18cfc09082a11c8","datavalue":{"value":{"amount":"+0.84845877","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$EFB13A42-4383-4430-8FAC-4C7A8D6C03CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08a4563f6233e45216d7e4ed047702f948e88342","datavalue":{"value":{"entity-type":"item","numeric-id":4548943,"id":"Q4548943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83d1ce962c70f41614974c2f56e1008b593197d7","datavalue":{"value":{"amount":"+0.8358722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$0F972420-E66E-4F18-B9DC-CE6661494179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e1aa5eefe35bb3f7d6e58bf43f7c04880a4aca0","datavalue":{"value":{"entity-type":"item","numeric-id":4788073,"id":"Q4788073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fad40f37fa6a0288e01ffe43acb2b2c5aa2e48b","datavalue":{"value":{"amount":"+0.82516146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$3DEBA4DB-B6D5-4DEA-8245-C2B9B76089A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1284c524c1bc780b31471641a254b6a78d80c10b","datavalue":{"value":{"entity-type":"item","numeric-id":3415878,"id":"Q3415878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae51f71d3ed1d1d81746e335c8c9416c024afd7b","datavalue":{"value":{"amount":"+0.82510734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$8E3CE5E8-7ED2-408A-A145-CC0EBF305486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba76ab369fa4c5466b7ed5f9a3ccf6dbe546f3b2","datavalue":{"value":{"entity-type":"item","numeric-id":1108932,"id":"Q1108932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"773f6b30faddc89063b04f21908457b5d1143219","datavalue":{"value":{"amount":"+0.8236498","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$C79AF372-8D4C-4EB2-8FC8-541174FC25BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"796c2f776dd6c7c6578c91d50bdc47f1a790d064","datavalue":{"value":{"entity-type":"item","numeric-id":1015301,"id":"Q1015301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5cbfd5a27417250af10b3922d4561b7f719c353","datavalue":{"value":{"amount":"+0.82360744","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$54938682-1914-4FB7-A925-F444946651B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6505a341913fe619dc2a3822986de1d3128486c","datavalue":{"value":{"entity-type":"item","numeric-id":3200892,"id":"Q3200892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d475b3f3d44cc1d41c9a4e5ea75ae40aca78e89d","datavalue":{"value":{"amount":"+0.81894803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794175$4CAD9105-1888-4290-AE97-CFCBE190B936","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:794175","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:794175"}}}}}