{"entities":{"Q1736596":{"pageid":1747337,"ns":120,"title":"Item:Q1736596","lastrevid":56792067,"modified":"2026-03-23T15:06:07Z","type":"item","id":"Q1736596","labels":{"en":{"language":"en","value":"Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042190"}},"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":"Q1736596$BDBE4E9C-BEA1-42B1-AA6E-4F70806B89F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e947be1134fb79f3b488d0e6f6f171daba86a91","datavalue":{"value":{"text":"Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736596$2DD9E4D7-CD76-4651-BC96-703814A56B15","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9c2ebbaffd15b352d433e0aa844f95df7e417bf4","datavalue":{"value":"1461.68153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$FE8A2212-A41D-43A5-B9CB-103C5924EFD0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc2203e7c18bf823149a1aeb37c3d62f1dfa4f7a","datavalue":{"value":{"entity-type":"item","numeric-id":1736595,"id":"Q1736595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$079E8C1C-10EE-4C14-AE20-BFBD32310D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"36bc2c2ff1bff875bdb9bdac8a4d467313fdf23b","datavalue":{"value":{"entity-type":"item","numeric-id":243597,"id":"Q243597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$181CB05D-6A17-4FE7-84EC-73B13050E298","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$C31867D6-3775-48AC-9367-84AF6C1B2EEB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-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":"Q1736596$0DACF356-A72E-45CE-8642-F44CA71BCCD9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d42aa40e9bfed443c6f853ab67e4483035459add","datavalue":{"value":"Summary: A key property of overlay networks is the overlay nodes' ability to establish connections (or be matched) to other nodes by preference, based on some suitability metric related to, e.g., the node's distance, interests, recommendations, transaction history or available resources. When there are no preference cycles among the nodes, a stable matching exists in which nodes have maximized individual satisfaction, due to their choices, however no such guarantees are currently being given in the generic case. In this work, we employ the notion of node satisfaction to suggest a novel modeling for matching problems, suitable for overlay networks. We start by presenting a simple, yet powerful, distributed algorithm that solves the many-to-many matching problem with preferences. It achieves that by using local information and aggregate satisfaction as an optimization metric, while providing a guaranteed convergence and approximation ratio. Subsequently, we show how to extend the algorithm in order to support and adapt to changes in the nodes' connectivity and preferences. In addition, we provide a detailed experimental study that focuses on the levels of achieved satisfaction, as well as convergence and reconvergence speed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736596$D036D5F1-B1A5-48A9-8937-BD2B23BDBC33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$5049C73C-C8B6-47C5-BEFF-A5CB23C839B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$91EBB73C-883E-48B9-9F6C-D5BB5288D76B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$E2F4384A-BE04-46ED-9ACE-F0373BCCA88C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$B5FB98AB-9129-4138-9061-CA43976CF4D9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"35f3484872c8d64fbd9e52ea0020293e9038da03","datavalue":{"value":"7042190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$6B89F400-409F-4DA6-BC68-89D1E089561C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736596$3A84D8A9-DCEE-4609-8B69-58503CCF3BDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53232568098fcf5e8435fa39cc3fa47db65029be","datavalue":{"value":"overlay networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736596$96C9F12F-395B-4902-966E-3D0907579754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"387e204c6977d7b097ac93bf9a6ecf723e21df10","datavalue":{"value":"distributed algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736596$C32DC9D7-455A-4BC7-AEA5-E19156A9FDBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6690f138360261f589949cb24c0b670b5e8d9b9","datavalue":{"value":"adaptive algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736596$FA414884-48CA-42B5-A3F6-E7051D388B17","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3636721609b071193ccc68847274676cb3c443c5","datavalue":{"value":"Q57583912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$C6ADE15C-53D8-4CFE-B282-C53C480A1093","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"db2849c9aa03ba6d507296d057305b9f691163b3","datavalue":{"value":{"entity-type":"item","numeric-id":54921,"id":"Q54921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$B6A79072-10E4-47A2-898D-093F7443472B","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":"Q1736596$0FF8DC30-51E5-48B5-90DE-180C9ADFC00A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"377dc0101846282a9fedbd4852f29cdb977d046b","datavalue":{"value":"https://doi.org/10.3390/a6040824","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736596$19EEBC13-DB5B-4568-9F38-57282A6C2D3F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1bfba54e4a78c0399242dbeffd3b62cc0f9489cb","datavalue":{"value":"W2005066278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$EF8C4420-AF59-40D3-AD31-D43707C31F68","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f392c05c994290c84a671d669f733e9edb62efd","datavalue":{"value":{"entity-type":"item","numeric-id":4938640,"id":"Q4938640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$4DFC7973-5218-4B88-9A1E-E6AA43989980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"349a79ba254311c619a204f46fda0f6e8e732405","datavalue":{"value":{"entity-type":"item","numeric-id":1605313,"id":"Q1605313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$EB8F2575-1BF5-45A7-A253-9AE83949DBC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1bddbce69bb87de6bb16b62bee72cddf7a0197","datavalue":{"value":{"entity-type":"item","numeric-id":3485870,"id":"Q3485870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$4040C145-BA20-492E-9F24-28D8D60B5332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dc3cc19598732eb8f92d76498eb0a87b0d181b9","datavalue":{"value":{"entity-type":"item","numeric-id":2384396,"id":"Q2384396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$494F3413-3716-40D9-BEBE-1A8E1603BEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9855b89f5bad4d5c2b38148d33dd23fe3b65b4e","datavalue":{"value":{"entity-type":"item","numeric-id":2944494,"id":"Q2944494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$D2454FA4-858A-4177-A81C-671EDE40B2CD","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":"Q1736596$E458DD0D-D3E3-439A-BAC4-35F7CB3996FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce8e0e6ed592abb65d66be1507447434133fa6ba","datavalue":{"value":{"entity-type":"item","numeric-id":5170310,"id":"Q5170310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$8C20C573-B26F-4C5F-A773-84BE3829D651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2319f34b67d55f1dfaf23255fd286305f1c2b32","datavalue":{"value":{"entity-type":"item","numeric-id":733718,"id":"Q733718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$30A14E5B-28F0-4FBE-8E5B-1351F8893B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f7f06ae9524634bd51bd90fd496fbe88810422","datavalue":{"value":{"entity-type":"item","numeric-id":3995616,"id":"Q3995616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$3E7F33ED-9883-4F62-93CE-7434FF256BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33578efeddab64e113a6d55a3ebccd4e42d0531e","datavalue":{"value":{"entity-type":"item","numeric-id":3581560,"id":"Q3581560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$BCFBBDA9-8DF7-4F8F-A56F-3771BCCA2746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"349d7ef85d935a77ed55af1929cb6c2c4498301d","datavalue":{"value":{"entity-type":"item","numeric-id":3101363,"id":"Q3101363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$1AA930CE-021D-4C38-A023-4CB70C78355E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$E98E6420-EE60-49AF-81B3-233701E3776A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$CE5DC4DC-1E95-4BC1-BB42-17938E2A0D01","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":"Q1736596$15136BFB-E6C4-42BA-B5D9-B9B5267F41CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd41a3d3ffce78a856861213ff6553c14d782cc0","datavalue":{"value":{"entity-type":"item","numeric-id":5904119,"id":"Q5904119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$2B9F117B-2D2D-4A07-825A-B3327C2E84B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16a207db0a5fb5fed5c95261511ad3a09a234bc9","datavalue":{"value":{"entity-type":"item","numeric-id":5401409,"id":"Q5401409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$155A836B-4551-407E-B265-510F0969D731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"703b737b87ed1e60d139fee4656c29b6b8fe3805","datavalue":{"value":{"entity-type":"item","numeric-id":5464202,"id":"Q5464202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$BA5E5D1C-F48F-457E-B11A-734E4EB6A93E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0eee40b127bc22089722a5a2e249294ee8dd3c3","datavalue":{"value":{"entity-type":"item","numeric-id":3177747,"id":"Q3177747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$94DB636C-5F8F-4735-888E-396576EDFC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff679834b2c825e7363253658156077f9a95bed1","datavalue":{"value":{"entity-type":"item","numeric-id":3646228,"id":"Q3646228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$44C546EE-4B24-458D-A43D-8957BEE4F536","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"49b3d5b5071987a0ca2b5a68c6e5076bcd77db62","datavalue":{"value":"journals/algorithms/GeorgiadisP13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$434945D3-F6A4-4861-9143-8ADF17BE354E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"30d089f7a161ac4538d03f25cfb9bafc269c81d8","datavalue":{"value":"10.3390/A6040824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736596$97379018-8CC8-49A3-A9EA-659F18D6714A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2858ff2eb43e36e423bb9c70240a2fd8290582e","datavalue":{"value":{"entity-type":"item","numeric-id":4636469,"id":"Q4636469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9270512330fbf0b60f0cf3646f97650ccb99cfb","datavalue":{"value":{"amount":"+0.7339085340499878","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":"Q1736596$8FA473E8-6355-447C-BA09-041E16500BC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa28c653d7b0928dc9d06df84877a787d769e884","datavalue":{"value":{"entity-type":"item","numeric-id":3174935,"id":"Q3174935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22f6712b24e407a6441e25ec84f0bda3c8a8608b","datavalue":{"value":{"amount":"+0.721528947353363","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":"Q1736596$7615DA7E-456F-44BA-88AE-F861B03C0B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9160c65a7acdebc7f8fc9d07e0550363e12d3d0b","datavalue":{"value":{"entity-type":"item","numeric-id":5401409,"id":"Q5401409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c25714da801a5302e00ba5dfeb15389e95188bf0","datavalue":{"value":{"amount":"+0.7140291333198547","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":"Q1736596$8CB613D9-DA0E-4300-9A0C-9BE040FBF7F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0b30a2a8c9600402d1121837e6b628c6521e2aa","datavalue":{"value":{"entity-type":"item","numeric-id":5101411,"id":"Q5101411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cfa8117f248332dbf61a8e2905de094392757a6","datavalue":{"value":{"amount":"+0.710540771484375","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":"Q1736596$8503502C-445D-4ACB-B555-B3895FC2A08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7f46a3bc6a6818adade9ad77efb274a8a6fb438","datavalue":{"value":{"entity-type":"item","numeric-id":2796247,"id":"Q2796247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a37946a8617c19de48362736c31e886bc5b5b8d7","datavalue":{"value":{"amount":"+0.7092717289924622","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":"Q1736596$87D4E62F-1980-47BC-9699-5CBA4AF3B589","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736596$5ED9C4DC-6D69-4816-816D-EB86A92B8D31","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736596","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736596"}}}}}