{"entities":{"Q1080871":{"pageid":1091623,"ns":120,"title":"Item:Q1080871","lastrevid":66850728,"modified":"2026-04-12T13:16:48Z","type":"item","id":"Q1080871","labels":{"en":{"language":"en","value":"On the existence of weak greedy matching heuristics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3968627"}},"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":"Q1080871$74CFEE9E-8C7F-404B-81E7-4AE6CFED7989","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"84ad2bf2576de84d75c7067dae39428e251e23a5","datavalue":{"value":{"text":"On the existence of weak greedy matching heuristics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1080871$FF69A3A5-2F6D-43D1-B379-6F37F24E9E22","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e95d87900a2252ebd164654b67aee405ff16bff2","datavalue":{"value":"0601.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080871$E9008B87-B50A-40FE-90C9-4658D6CF84DF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"23f99f8fbc48dc952bd9661f74f02683da854f0a","datavalue":{"value":"10.1016/0167-6377(86)90078-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080871$1B9D23D6-0BD5-4A35-879F-A2B0D6E518E2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$F54E7F6C-6560-4CAF-8A1E-A139CDEE8FA9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$BDE60ADF-365A-44B9-A87B-EC9C090BF96D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1080871$34B25B96-D833-4EDA-8E21-2A21C2D096C0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f350b194303d57f05614231dc6d8ab12a2776feb","datavalue":{"value":"We exhibit an exponential number of greedy heuristics for minimum weight perfect matching of complete graphs of n vertices with edge weights satisfying the triangle inequality. The ratio of the weight of an approximate solution obtained by these heuristics to that of an optimal solution is shown to be bounded above by finite and valued functions which depend only on n.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080871$2726ECBB-E0DE-4FC3-8638-E207A790A58D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080871$2D46722E-50CC-4747-BF28-BD50D9109CBE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2b09916c28f0cdd685b06b2c50db62f9cb8c8106","datavalue":{"value":"3968627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080871$33016F29-C533-43F5-A652-D7D8B15C1536","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b037e835bec10946c8275121512d8f5f0a03729","datavalue":{"value":"approximate algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080871$7491ED63-3EC7-45B7-A5AB-AEFE09B744CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080871$074AD87F-694F-4101-A516-03FC2235CE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080871$F68EECED-8494-494A-A3FC-F5994CA444CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e374d8525238efe155d23fddd171f6c6d9279fc7","datavalue":{"value":"minimum weight perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080871$4C18478A-D5FF-48BD-8DD4-9A4DA364D9B8","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":"Q1080871$0C51B88C-CD39-4573-9E7C-E207D9CEAC6F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7db4956fc7d26a9cec4727d8eb0e8a651de78140","datavalue":{"value":"https://doi.org/10.1016/0167-6377(86)90078-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1080871$45A8A0D5-8B50-475C-9F6D-A4348031C0AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e6123f758a248d932fbef3ade22b6dab215d0abe","datavalue":{"value":"W1987379377","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080871$8A8047C7-E818-4C39-9B67-A191FF788FD7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d99b6b1510cc48c01add15e4d9b0ddec53d7dad","datavalue":{"value":{"entity-type":"item","numeric-id":3315292,"id":"Q3315292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$500670BE-B76B-4A78-9293-11482C9D7F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ce89c39eded45d5a7a9d9cb06ace1eda77c8a8","datavalue":{"value":{"entity-type":"item","numeric-id":3911409,"id":"Q3911409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$F31B8C96-6EFA-4A5A-849A-257DFCB4E1D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15ccd1c6e44d65eb4acbc8daad6efebdf54c3737","datavalue":{"value":{"entity-type":"item","numeric-id":1141079,"id":"Q1141079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$7FB15E0F-4810-4F55-9D81-A47E1068257F","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":"Q1080871$F577D3C0-6709-4341-9B20-A8CD4102066C","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":"Q1080871$E0174187-27AA-495C-A77B-09140FE3B05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d60e08211526fa506255eacbf5e31b7600d8396","datavalue":{"value":{"entity-type":"item","numeric-id":1072708,"id":"Q1072708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$1C114C99-8E45-4F07-BF68-1BAD21DED47E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be3bc2760abaf4a42d49a62872626594d9d5ba2e","datavalue":{"value":{"entity-type":"item","numeric-id":1152226,"id":"Q1152226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$9765118D-3CB6-4EDC-BD1A-BFFA0B37EBD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$B50F3E49-E5F4-4FD5-8219-F5F12F00E801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7534d88e63231e4bb12474e9051539230aa7343","datavalue":{"value":{"entity-type":"item","numeric-id":3332259,"id":"Q3332259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080871$56721EC4-FC38-4084-88B8-D744496EE28D","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":"Q1080871$83C99122-A77A-436E-9256-6680E3059186","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"444cc5df2fbb4ba4fe5782cc1301fc156106a0c6","datavalue":{"value":{"entity-type":"item","numeric-id":3782810,"id":"Q3782810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04960d75822936d3405ad41c185e0030cdc7aaac","datavalue":{"value":{"amount":"+0.9313784837722778","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080871$02A4C7C7-AE18-4704-BA9A-0587481ADD11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21fdcbacd538c6f97fde957b9544d94e1bba595e","datavalue":{"value":{"entity-type":"item","numeric-id":3813310,"id":"Q3813310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7574c51fef134fb9f2307b13b378d9e558e695ac","datavalue":{"value":{"amount":"+0.8844068646430969","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080871$1D1B89EF-EB02-422D-B2A5-43AF14F111A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e07f4c50da02a3d142f478c1f4282e81d986068","datavalue":{"value":{"entity-type":"item","numeric-id":4731220,"id":"Q4731220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33905aef30ba0a1d8c1289d527f17dbf5326fd34","datavalue":{"value":{"amount":"+0.8808329701423645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080871$0F4846F7-750D-4607-9490-566FC0A668EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47cf76907fd9604e9bd8a05070ef962e8f4d0dfc","datavalue":{"value":{"entity-type":"item","numeric-id":1361421,"id":"Q1361421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636bdc6af399febf6373f90eb76e1a8712f442cb","datavalue":{"value":{"amount":"+0.8712970018386841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080871$2EC4945C-12F6-412F-BD1E-E96FBA94767F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cd91d5b4d785d4ba26ce4344f24d389047cc48f","datavalue":{"value":{"entity-type":"item","numeric-id":3474883,"id":"Q3474883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636bdc6af399febf6373f90eb76e1a8712f442cb","datavalue":{"value":{"amount":"+0.8712970018386841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1080871$6D1E7C5E-5218-48CD-BCB4-17248FEF265C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the existence of weak greedy matching heuristics","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_existence_of_weak_greedy_matching_heuristics"}}}}}