{"entities":{"Q473162":{"pageid":474929,"ns":120,"title":"Item:Q473162","lastrevid":62087898,"modified":"2026-04-11T03:41:20Z","type":"item","id":"Q473162","labels":{"en":{"language":"en","value":"Belief propagation for optimal edge cover in the random complete graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6371854"}},"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":"Q473162$73CD58D1-E75B-4349-95FE-059A98D0FC57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d96fa1fa577cc9885868cfcd80392ce7e311992","datavalue":{"value":{"text":"Belief propagation for optimal edge cover in the random complete graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q473162$A2890888-48BE-4242-9B9E-30896BE196C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6024842af1f194460d8aa60ce88c50601417d611","datavalue":{"value":"1318.60016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q473162$3FF1857D-2F98-4827-92E2-70407F0EF072","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d708d266b636aa152216dade6f272af0b7c06830","datavalue":{"value":"10.1214/13-AAP981","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q473162$00FAA6B2-925D-426A-9CB8-60EB9991E67F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1c2e889b5cf140d3aaef1988abb42e8627946f1","datavalue":{"value":{"entity-type":"item","numeric-id":473160,"id":"Q473160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$FE7BBA15-A012-44D2-AC19-B7820FAAB547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ef7285f5a885c16ec50d7b7466833c84b364544","datavalue":{"value":{"entity-type":"item","numeric-id":473161,"id":"Q473161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$2F500E78-13EF-40E2-8BB3-2BC11DA2DC3B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e04a4b352e727282a8f30f5809a3df145fda07dd","datavalue":{"value":{"entity-type":"item","numeric-id":81240,"id":"Q81240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$B12D076C-E91D-4251-9396-5C86C284A201","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"899d0c07a87e80e5a99f3b903edfcb19ef7c5cda","datavalue":{"value":{"time":"+2014-11-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q473162$2F7D8CAD-EF88-4DAF-B030-641009C0A3B0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1cc659004e224c54cdfb7a9287afc1a87f901c40","datavalue":{"value":"https://arxiv.org/abs/1212.6027","type":"string"},"datatype":"url"},"type":"statement","id":"Q473162$36E1B6C2-CAB0-4334-A2E8-8F7EB96F0829","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a64b9864a0c7d4cbb50e28d35057381be510ab4","datavalue":{"value":"https://projecteuclid.org/euclid.aoap/1409058036","type":"string"},"datatype":"url"},"type":"statement","id":"Q473162$F1C2A0A4-827E-4487-9E75-FE251B94DF7C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9bedb02db1a218d1d5fd2ef5e3783a694d99e810","datavalue":{"value":"This article studies the minimum cost edge cover problem on the complete graph, where the edge costs are random independent and identically distributed. The article begins with a review of the literature on the problem, followed by a presentation of the main result which is the limit of the optimal cost as the number of vertices goes to infinity. Moreover, it is established that a belief propagation algorithm, presented in the article, provides an edge cover which is asymptotically optimal as the number of vertices goes to infinity. The authors provide a very large number of useful results via proven theorems. A list of useful references concludes this interesting article.","type":"string"},"datatype":"string"},"type":"statement","id":"Q473162$0041A6D5-0E52-42F2-AF04-E9F322F987EE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58309c80337e7309a39fa8b39c69e1b722b3cd2b","datavalue":{"value":{"entity-type":"item","numeric-id":590170,"id":"Q590170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$83ABD4C0-DA70-45D6-B083-AA544D9140DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q473162$14335BD2-F13E-4295-8581-AC4C8E114609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0dd26fa594336927a7a04e8147a405d69e5da239","datavalue":{"value":"68Q87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q473162$00F2B221-93F9-4935-8396-12A4B58DFD15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"764fa64170867068d32ec5e87c04ca51fa63a306","datavalue":{"value":"82B44","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q473162$8DC64FB2-2F04-4B6F-827F-B258F567FEFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q473162$8D565E75-1E60-4E50-A8BA-D91C58697044","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3c96d2ccc22a141f414e96ef2c7215b411ac753f","datavalue":{"value":"6371854","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q473162$13E73CFD-77BC-4246-9102-EB90BAA1526C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0736c3a2794a43ca9b54a65436cbd71cf0796887","datavalue":{"value":"belief propagation","type":"string"},"datatype":"string"},"type":"statement","id":"Q473162$C18B3B36-E784-4BBE-B3BC-15C15A54071B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ce2443a5ea0ca561ca307264f4427ddea6396c8","datavalue":{"value":"edge cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q473162$883FE57E-A6FD-47DE-AA06-AA3219695861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5933f1257e4d05ccca7ccddcc166bec14b0c116c","datavalue":{"value":"local weak convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q473162$56094E59-2E3C-46AB-86CF-0C3BF43A14F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30bcce1c04a93da2f7201ec96c6aed636fc63892","datavalue":{"value":"objective method","type":"string"},"datatype":"string"},"type":"statement","id":"Q473162$FB9F442D-64D5-4DC5-BF90-182BBD327CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79e0e0338ab4ad2b78b61c4e4b8a69d54660e7ab","datavalue":{"value":"semantic projection","type":"string"},"datatype":"string"},"type":"statement","id":"Q473162$485F0109-ACEC-4055-9F8D-050DE2D42408","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":"Q473162$40BBB1DE-C8E1-43CF-B9E5-610F0155629A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d131241905d2099fe11b56cc59c838df260f6f66","datavalue":{"value":{"entity-type":"item","numeric-id":1203927,"id":"Q1203927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$E9DE7D0F-F544-4D03-9ABD-E3B1EF63E5EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8078c945dc936fe9c2e53691f0c1370b3fcc964e","datavalue":{"value":{"entity-type":"item","numeric-id":2462018,"id":"Q2462018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$E395A3DC-18F8-4FA5-BB6A-31EBF0F33542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe3ac3bc3b4417df2dfa8a76e182a4a1b02d36bd","datavalue":{"value":{"entity-type":"item","numeric-id":4450065,"id":"Q4450065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$FE727ECB-8282-454F-B797-6AC08FC7985F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c75f1b5517e4acfdb89634dc8c32222fc0620f9","datavalue":{"value":{"entity-type":"item","numeric-id":2746215,"id":"Q2746215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$810E3CFD-7FCB-4D46-92AB-B7ED5D6FF290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63515a8438cea0e13c743fa27fdc4f1973f18dc6","datavalue":{"value":{"entity-type":"item","numeric-id":558662,"id":"Q558662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$E219594B-7D68-4DAE-94C8-8DF51EA73B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34f25af03a74daf672b74d5991d5eb04a6ede221","datavalue":{"value":{"entity-type":"item","numeric-id":537683,"id":"Q537683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$3B7C4009-44DB-4D4D-AEE2-476653AC69FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f008281c0b714907bb438c8e1a9931f0cb8b9d0","datavalue":{"value":{"entity-type":"item","numeric-id":3604573,"id":"Q3604573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$7C37ABE0-BF16-4734-AFBF-CEFFBD271D35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a270b91c4299553b6f90d4713b498e1c7fd02458","datavalue":{"value":{"entity-type":"item","numeric-id":1066149,"id":"Q1066149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$786CD101-E88F-4A11-879B-B26FB2862FE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6d524b5e95bab83f322bb147d1cbcb44d745841","datavalue":{"value":{"entity-type":"item","numeric-id":3204318,"id":"Q3204318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$3DC343F1-04A4-4172-97B7-1A763C2F1331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90f0098618269911e7bd13e4b8c2abdc4d67313d","datavalue":{"value":{"entity-type":"item","numeric-id":638371,"id":"Q638371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$9CE9D3DB-B8A0-4243-B57C-E520655D7740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f0d3a58f0b7605da288576d52a4ea55c928f729","datavalue":{"value":{"entity-type":"item","numeric-id":3651488,"id":"Q3651488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$F20D3549-682F-4545-AAEB-CF715742A426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"deda57f933fbed277bb80fb09059d582dbe95f59","datavalue":{"value":{"entity-type":"item","numeric-id":3169045,"id":"Q3169045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$F3C6D868-2680-483B-A57A-8B936231854B","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":"Q473162$6FC7EE04-BB4A-4879-8CD1-8E7CAA1F0545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd9030a8ba05045ff32d1fcc550f5ccceaaae8aa","datavalue":{"value":{"entity-type":"item","numeric-id":617874,"id":"Q617874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$1441C4EA-7E09-4BF3-B9A3-6DF4A3A59DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8338c18a30355541f4063bbbf1d6a046dba82eb7","datavalue":{"value":{"entity-type":"item","numeric-id":431636,"id":"Q431636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q473162$25A2FDB2-023F-491F-9647-4F6257CCE76D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16d88a0058e80a18b15a582c8f01f302c6cb6608","datavalue":{"value":{"entity-type":"item","numeric-id":3169045,"id":"Q3169045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cb92a05eab15fa6eabdf6bb2eef226d80f685c4","datavalue":{"value":{"amount":"+0.8139537572860718","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":"Q473162$FEA4492B-4881-40A2-A7C2-79C7DD3F4AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"837ce36d69d9dfe7ff2b69a33b00995188340bfc","datavalue":{"value":{"entity-type":"item","numeric-id":2514304,"id":"Q2514304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eca3f9a7edda1071deafe09f04cab125e22234fb","datavalue":{"value":{"amount":"+0.7932131290435791","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":"Q473162$00155560-AAEF-4831-8AD6-864A3A73B33C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cb53c2dd419fe09a5785bc6f5939f31b3b9b3d5","datavalue":{"value":{"entity-type":"item","numeric-id":4633825,"id":"Q4633825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c19954182db3bde8befffc7d843106666f23edd","datavalue":{"value":{"amount":"+0.7841968536376953","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":"Q473162$AC27530E-14A2-4258-A2D6-8F61514D727A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e7c376dc0904045831eacfdb1c7005fc8fa5efb","datavalue":{"value":{"entity-type":"item","numeric-id":638371,"id":"Q638371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3c58dbc1c9a52c2066897a2a73f323badd9a37d","datavalue":{"value":{"amount":"+0.7603018283843994","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":"Q473162$82B53C82-45C2-407E-A0C9-A01A39FFD89E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8ff96a05bd062c00f1c6c161063fef33ec5da0d","datavalue":{"value":{"entity-type":"item","numeric-id":3094953,"id":"Q3094953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a95c7116f9968184e11a760b664c95b0eb7e350","datavalue":{"value":{"amount":"+0.7335060834884644","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":"Q473162$84726C9C-68EC-4C0B-A492-F9EAD026DF51","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Belief propagation for optimal edge cover in the random complete graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Belief_propagation_for_optimal_edge_cover_in_the_random_complete_graph"}}}}}