{"entities":{"Q2428674":{"pageid":2439417,"ns":120,"title":"Item:Q2428674","lastrevid":73402380,"modified":"2026-04-14T15:47:50Z","type":"item","id":"Q2428674","labels":{"en":{"language":"en","value":"Weighted matching in the semi-streaming model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6028430"}},"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":"Q2428674$8C6ADA37-4AFE-4233-9326-9B3E728C3CD5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eca0545211a47bf052f8a0afdcc9b7d09d73cf67","datavalue":{"value":{"text":"Weighted matching in the semi-streaming model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2428674$DE250393-31D7-4FD0-92EA-F3164A78E998","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6a2a216e055da4c259bc991d3a197a7b79f5dfd5","datavalue":{"value":"1246.68266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$E3C2F36F-E519-488F-B516-A5742D088528","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebaa54630a45ffc566cd660214f4ec90de00a4aa","datavalue":{"value":{"entity-type":"item","numeric-id":621920,"id":"Q621920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$029E47CF-0DCE-40B8-BEC9-9A9F060C9A19","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$DA177B3F-D96B-4D97-869B-21002D1C9B0C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"52b04daa1d703ea977748e4d42defef3819c2dd9","datavalue":{"value":{"time":"+2012-04-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2428674$34096DF0-30CF-4177-BCA4-3BCC11FBA992","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"22b47100f445bb8781eb410c0456425474f07c48","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2008/1312/","type":"string"},"datatype":"url"},"type":"statement","id":"Q2428674$4F71BD36-BCD5-4A4F-915E-3058F4F9DDDC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a76ef6601461e1e4c19b719fd3668198d2d773f0","datavalue":{"value":"A simple algorithm for the maximum weight matching problem is analysed. The \\(m\\) edges of the input graph on \\(n\\) vertices are given one by one and carry positive weights. The local memory consists of \\(O(n\\log n)\\) bits; see [\\textit{S. Muthukrishnan}, Found. Trends Theor. Comput. Sci. 1, No. 2, 126~p.\\ (2005; Zbl 1143.68385)] for this model. The algorithm maintains an initially empty matching \\(M\\) consisting of edges known so far and remembers for each edge in \\(M\\), up to two, shadow edges it displaced from \\(M\\). For a new edge \\(e\\) let \\(A\\) be the set that consist of \\(e\\), its potential shadow edges, and their shadow edges. To handle \\(e\\), \\(M \\cap A\\) is replaced by a maximum weight subset of \\(A\\) that forms a matching. This gives an approximation ratio of \\(5.58\\). \\textit{L. Epstein} et al. [SIAM J. Discrete Math. 25, No. 3, 1251--1265 (2011; Zbl 1237.05163)] achieve \\(4.91+\\varepsilon\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428674$D17C2AFC-1F01-42F8-B47B-A83583B019B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$993E1812-7A6E-4882-B28E-CEF5A44DC370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$0BFC5E65-C7C4-4AE1-951D-3596E6B95FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$9545D79B-8163-4251-8C36-247A7AB1F6DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$A372D025-524E-4F91-9996-3DA4A7B3268A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$C4AE1E8D-879A-4764-BC58-1A81E0C89462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$9C5C2D55-A23D-4B5C-A814-6A517AEC027E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$0EE7E742-BD2B-4928-AB2E-717133B6F42F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0ba511223297fba1264ef51a42f63a5d220a1fc","datavalue":{"value":"6028430","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$4D1950E8-72F5-4296-A90B-95EB65A59DC1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4259cdffed1c46afe326a781a3aded90c8112617","datavalue":{"value":"semi-streaming algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428674$F8F5E264-92E5-4F50-B82F-2DC74E94105F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428674$BF556119-E05B-4CB8-8848-EED26D64EE51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428674$2741C8B2-24D2-402B-AD64-82791E60313F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428674$F726FB92-0684-4341-A534-37106F77167F","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":"Q2428674$B252C64D-D295-4780-9122-3B67850D6578","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9601ecb1f3e7bca2cdeef8c4e1a9b5a1942fb73b","datavalue":{"value":"W1498807656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$D324EDA1-3D7D-43B4-90DB-1FDA73B62ECF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6204e56589df344691ffc7534bf94bce6a69259a","datavalue":{"value":{"entity-type":"item","numeric-id":2944492,"id":"Q2944492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$E0AC37B8-2A17-4D1B-802C-23F4A97BD900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"157ca85661c4abdae2f0d8c918c819c6dd17806b","datavalue":{"value":{"entity-type":"item","numeric-id":3113762,"id":"Q3113762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$9C826468-0112-4ACB-940F-9B65720ACF1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a8da16e62b9b09c054a7ffe0a52eec18c0c193d","datavalue":{"value":{"entity-type":"item","numeric-id":5466491,"id":"Q5466491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$DA0E4E7E-A5CD-43FE-A8B8-ABB73BB56295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5327ca07f3faf9bdfc1fb6581fe1f84641e845","datavalue":{"value":{"entity-type":"item","numeric-id":2921736,"id":"Q2921736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$8AFF908F-9760-44C8-840F-3F18D12B6E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb17a28cc43d842c9db5f945e5260121e7b7f4cb","datavalue":{"value":{"entity-type":"item","numeric-id":3138921,"id":"Q3138921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$B0B469F5-F1A3-4F68-9876-F0C2676BF545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"267749dd6974655fa3381e8eb6691edb51eb0114","datavalue":{"value":{"entity-type":"item","numeric-id":4945538,"id":"Q4945538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$D4F1CCA0-FB76-4C94-8C66-3713D5E3D8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cc53b8c0488bef8d6e5dc146daf66876208acbc","datavalue":{"value":{"entity-type":"item","numeric-id":5479368,"id":"Q5479368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$B2A99134-C4E8-47AC-B731-25AB1A7984C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7149c2200c2477acc79be9919840daa502da44bc","datavalue":{"value":{"entity-type":"item","numeric-id":1969949,"id":"Q1969949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$6B16561F-5AEE-49F4-8768-21067FFB6E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5207b2e2e6fa3bbd01b48889f1444981c7d441bb","datavalue":{"value":{"entity-type":"item","numeric-id":1583343,"id":"Q1583343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$314BEB0A-B53F-4129-A843-67C8339AA820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab55912bde4ac461b67aa1060ea23f38f2f798d7","datavalue":{"value":{"entity-type":"item","numeric-id":3425115,"id":"Q3425115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$DE58AEAB-E7E7-40DA-8DC8-82DA4E09AF1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6905162edf52ce30b45781be5d5eb535cdbcc74","datavalue":{"value":{"entity-type":"item","numeric-id":2390325,"id":"Q2390325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$47ABC1F6-A94A-4637-8973-43ACE6DA755A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59c29c4e34d36e7e5ccbb8e271573506005489a4","datavalue":{"value":{"entity-type":"item","numeric-id":4251057,"id":"Q4251057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$2E386D3E-7431-4EA2-BCBA-9B3443819ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c01149a6900c0f611a509645affd60c9a396109","datavalue":{"value":{"entity-type":"item","numeric-id":1854113,"id":"Q1854113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$4D33F713-8DFB-47B2-AD92-6EA14D9F2688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4c4ac1ff262b0220218571e1cf2cc6a79d8d813","datavalue":{"value":{"entity-type":"item","numeric-id":2380006,"id":"Q2380006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428674$3DCA1404-C61C-4EA6-8413-DC512C5D7AFE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2dfa98837b551c3154fd02332a0a64bb7bbe352c","datavalue":{"value":"10.1007/S00453-010-9438-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428674$2E3DC7E5-4468-4518-986F-03410E4BFD63","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2507874fe8012c7292915e2beaeaa86dea3cae0b","datavalue":{"value":{"entity-type":"item","numeric-id":4910759,"id":"Q4910759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb54f09ab06f3391569fb05d0c12f90a341b7564","datavalue":{"value":{"amount":"+0.9846972823143004","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":"Q2428674$C93C299B-3DA0-45D0-850B-1F929D53F430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f057b71ff38fa6c3b9232bb3634511ee3028089a","datavalue":{"value":{"entity-type":"item","numeric-id":4629986,"id":"Q4629986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c536b8c089551dfd3548e6463a2fa26930e31372","datavalue":{"value":{"amount":"+0.9293064475059508","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":"Q2428674$89345B96-4A4D-41CB-A8F6-EA35333A6F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4865f9ebc2a6dcb98b2f815abd25cc1e67f62949","datavalue":{"value":{"entity-type":"item","numeric-id":4575888,"id":"Q4575888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f40dca2d015c32dc3179f3796948319792503c6d","datavalue":{"value":{"amount":"+0.9278175830841064","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":"Q2428674$20F2FA1B-1EBE-4B23-830C-E6B85D1B6835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"559d5775fa8f8b7591fc4343c006caaa070097d2","datavalue":{"value":{"entity-type":"item","numeric-id":3113762,"id":"Q3113762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1fe10fc2ac3f28fc1881d7b274948edd7f19e1b","datavalue":{"value":{"amount":"+0.9174665212631226","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":"Q2428674$7951659C-5BA6-4AEE-A442-4569AF7277EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78893386645cb743b9a508c3596106030dbaec89","datavalue":{"value":{"entity-type":"item","numeric-id":3225117,"id":"Q3225117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6716f1471bd41d19a9efb84763d1e3703e613033","datavalue":{"value":{"amount":"+0.9166882038116456","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":"Q2428674$6BF81F32-1FE7-4A15-BC05-DEF474FADED4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Weighted matching in the semi-streaming model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Weighted_matching_in_the_semi-streaming_model"}}}}}