{"entities":{"Q5896750":{"pageid":7936993,"ns":120,"title":"Item:Q5896750","lastrevid":49767982,"modified":"2026-01-10T12:58:30Z","type":"item","id":"Q5896750","labels":{"en":{"language":"en","value":"Efficient schemes for nearest neighbor load balancing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4219143"}},"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":"Q5896750$B2B6B662-D34F-447F-AD45-EF612E56BE53","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b26fdfc49e6b1bc41bbb688318eb56ab3acb38fa","datavalue":{"value":{"text":"Efficient schemes for nearest neighbor load balancing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5896750$AF1D6997-8D1E-4FA1-952F-1E9C35131CA0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fad1d2d77a6d2c5593ef13b82ff64b2eba63832e","datavalue":{"value":"0942.90023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896750$5E41F103-5F1D-4923-BE5F-1F828CD0AFF8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a2df47b32ac15627d8c941d44bf19c83ce2c5b40","datavalue":{"value":"10.1016/S0167-8191(99)00018-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896750$B9A645AA-8643-4B86-BEA2-5E4B657C2D26","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d65bb5820f4b553813b40ced47994c613a909d65","datavalue":{"value":{"entity-type":"item","numeric-id":202550,"id":"Q202550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896750$FE72D05F-AACC-4BB2-B536-4CB1DC040FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b9f391e6322208fe1ff9282b50ef9e948c0574c","datavalue":{"value":{"entity-type":"item","numeric-id":284584,"id":"Q284584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896750$E486E731-4C17-45ED-9010-B30ACAD8FE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"217f37161c659d7a99a4775b22fa0f333e3f44be","datavalue":{"value":{"entity-type":"item","numeric-id":1960451,"id":"Q1960451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896750$EFFB1C31-E853-4421-B365-7B1ABEC12EC2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"eeac13f60c55bdb04ecb49274cc7b24a1688345d","datavalue":{"value":{"entity-type":"item","numeric-id":71527,"id":"Q71527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5896750$30A054BA-D747-44DD-A52C-0918B1178852","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4807edd6e640ad656e01e00a44b61d620e873df6","datavalue":{"value":{"time":"+1999-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":"Q5896750$EA2DD3B1-2558-4B21-9485-C9DA824A4CDF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"acfbaabb3ef8edadd1b4c1d2da6ff8acfe169c62","datavalue":{"value":"We design a general mathematical framework to analyze the properties of nearest neighbor balancing algorithms of the diffusion type. Within this framework we develop a new Optimal Polynomial Scheme (OPS) which we show to terminate within a finite number \\(m\\) of steps, where \\(m\\) only depends on the graph and not on the initial load distribution. We show that all existing diffusion load balancing algorithms, including OPS, determine a flow of load on the edges of the graph which is uniquely defined, independent of the method and minimal in the \\(l_{2}\\)-norm. This result can also be extended to edge weighted graphs. The \\(l_{2}\\)-minimality is achieved only if a diffusion algorithm is used as preprocessing and the real movement of load is performed in a second step. Thus, it is advisable to split the balancing process into the two steps of first determining a balancing flow and afterwards moving the load. We introduce the problem of scheduling a flow and present some first results on its complexity and the approximation quality of local greedy heuristics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896750$6B577FDC-8886-4CA2-920C-8E0B3F1344DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896750$47B54ACB-7863-44FC-8395-B63336E3C46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896750$3B92802E-AFF7-4925-9310-F29C51A5B45E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"430661c4d52eacfb49cbea80be432a65a285b9c8","datavalue":{"value":"4219143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896750$F5804DD9-78D0-4842-A5A7-B6320A7F0951","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a4693628af44fd07a379e870acd8dd348235245","datavalue":{"value":"nearest neighbor balancing algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896750$D989ED04-27F4-461E-B7A8-B9CFC0D98DD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62697a34ee961994a95cdf62be1d0cecf3aa23e5","datavalue":{"value":"diffusion load balancing algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896750$FABC3B85-7E9E-4583-B7F2-89AA47A6EA44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70aa9f35e50da405459849f6d49bcf6f3c96bb62","datavalue":{"value":"optimal polynomial scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896750$405F1ABB-95F1-4736-B5CD-4D8FA2447B43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896750$D9278FFF-672E-4D8A-8ECA-AED76705B151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"581bc451a58893b4a34d84c80bde9c3a3a1ff43a","datavalue":{"value":"local greedy heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896750$B2F55B24-BA9F-4301-A975-E403DC530FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ccfcf3a8f1df4738b1d1df54c8e9fe9a0075dc0","datavalue":{"value":"OPS","type":"string"},"datatype":"string"},"type":"statement","id":"Q5896750$48404C00-CEAC-4898-A778-48E061993FAB","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":"Q5896750$C72F7FC3-2235-460E-B6AE-E7486090F610","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f18b7a4d4051968b9f944cdc55b34c42129d78c","datavalue":{"value":"https://doi.org/10.1016/s0167-8191(99)00018-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q5896750$413B5777-8F4F-4E66-AD2E-095A05AE23D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bfc80bd61c5979ac693f0fac7d603a811c3226d7","datavalue":{"value":"W1985451401","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5896750$550A5221-52F0-4439-9903-C300F4C375C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7caad1ff280dd7ca972ed1cb23f1ef967af36e53","datavalue":{"value":{"entity-type":"item","numeric-id":5917954,"id":"Q5917954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cca9195cfbc8a8e267a86b1a5b262270e17d05e","datavalue":{"value":{"amount":"+0.9991950988769532","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":"Q5896750$3E923DEB-081F-4970-A4FD-DDEB3DA5850A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d7bdd66c9c7a41710c8fdea539be8c1636ec8cb","datavalue":{"value":{"entity-type":"item","numeric-id":4252039,"id":"Q4252039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa63782f7d7d1937827ecb1f391c6d86fd3d47e0","datavalue":{"value":{"amount":"+0.9854041934013368","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":"Q5896750$05D79440-A86E-4585-B306-5B3CE7B220DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b302f7abfd1aec9dbe9a39ffed68e4234cf22bc0","datavalue":{"value":{"entity-type":"item","numeric-id":1849576,"id":"Q1849576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa63782f7d7d1937827ecb1f391c6d86fd3d47e0","datavalue":{"value":{"amount":"+0.9854041934013368","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":"Q5896750$CED1EE8D-7C3D-4FEE-90D5-47F136C48593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1efc4de30b735e6f64629588dd0824711ab2a49","datavalue":{"value":{"entity-type":"item","numeric-id":4945781,"id":"Q4945781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68a2d68f26aee519d5dadd011f28fba3f0c527d5","datavalue":{"value":{"amount":"+0.8766588568687439","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":"Q5896750$63459E71-166C-4002-9872-86F31F5AA091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a082c33876b62308fac0811030b3aa53ac0034a3","datavalue":{"value":{"entity-type":"item","numeric-id":1606864,"id":"Q1606864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68a2d68f26aee519d5dadd011f28fba3f0c527d5","datavalue":{"value":{"amount":"+0.8766588568687439","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":"Q5896750$408BFBD1-CB38-4097-ABCD-8982C2C68F84","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5896750","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5896750"}}}}}