{"entities":{"Q1853151":{"pageid":1863893,"ns":120,"title":"Item:Q1853151","lastrevid":71501370,"modified":"2026-04-13T22:40:58Z","type":"item","id":"Q1853151","labels":{"en":{"language":"en","value":"More on random walks, electrical networks, and the harmonic \\(k\\)-server algorithm."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856487"}},"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":"Q1853151$628F56CA-91C2-4E59-87C5-5707695C12FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e4a7d49a1fcaf35297e479174430401cca00df8","datavalue":{"value":{"text":"More on random walks, electrical networks, and the harmonic \\(k\\)-server algorithm.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853151$3F5DA34A-02E0-4FCE-9F33-FA651E7073ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8883e34543d452902ae5caf7cc98376785f5f022","datavalue":{"value":"1042.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853151$DB696D11-56E8-4E12-B6DA-EE28B55A8CE0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"539a75cc65b535844b7960854baf388693cfcdd3","datavalue":{"value":"10.1016/S0020-0190(02)00287-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853151$3DAEEF3E-E763-4913-B8C6-460F5819A2F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97f37dc983198355fd189ee54af7058c412c3222","datavalue":{"value":{"entity-type":"item","numeric-id":287139,"id":"Q287139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$961F3672-B062-4D03-8842-52C51F221DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f25e28ff0340915ed4ca0acf01c43315ac149a40","datavalue":{"value":{"entity-type":"item","numeric-id":189395,"id":"Q189395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$C1BA006F-5123-4E75-BC93-5A6559141B62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b0fb0f2c86e93cd39417ea5519157255e289364","datavalue":{"value":{"entity-type":"item","numeric-id":222782,"id":"Q222782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$0B061A21-E840-4736-81F5-3F7D9D524A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6441b04c78f0db4705bdccbf7117dee8afcd822d","datavalue":{"value":{"entity-type":"item","numeric-id":388454,"id":"Q388454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$628EC8C5-6713-454C-A485-F19018450941","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$74AD568C-DD67-44E8-B34F-008DD1BE5FB6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-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":"Q1853151$B4EFC5CF-2FBE-4492-9069-F419BBD01087","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be5d6617a4393d8bc97b20efcb47abc6f321be8f","datavalue":{"value":"Techniques from electrical network theory have been used to establish various properties of random walks. We explore this connection further, by showing how the classical formulas for the determinant and cofactors of the admittance matrix, due to Maxwell and Kirchoff, yield upper bounds on the edge stretch factor of the harmonic random walk. For any complete, \\(n\\)-vertex graph with distances assigned to its edges, we show the upper bound of \\((n-1)^{2}\\). If the distance function satisfies the triangle inequality, we give the upper bound of \\(\\frac12n(n-1)\\). Both bounds are tight. As a consequence, we obtain that the harmonic algorithm for the \\(k\\) server problem is \\(\\frac12k(k+1)\\)-competitive against the lazy adversary.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853151$D488D744-FC4E-4F1B-AB4D-61B47C32D2F9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853151$F9A9A954-6256-413C-88B2-555FD2304BAE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ea09c9d3a61bb8cf29888bba9775eab31fa5d74","datavalue":{"value":"1856487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853151$C2BD066C-AC36-40C4-8144-5BC97EC2C2DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a362ce090b25a564d589edc558e4bd1266d9df9e","datavalue":{"value":"Analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853151$D23023A5-A5EA-404F-B634-F5D693B0325F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e39807ce65c97d0e0263e18a3816f84213a6ec1e","datavalue":{"value":"Theory of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853151$9896106D-7522-4799-8533-6DC949DBD72F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"574e227dcc908033533aea0ceec697f16797a601","datavalue":{"value":"Randomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853151$01FA2EE4-CE21-4DB5-B415-6196FBF2E58E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"571e394af377384e082609d4e7439e28e0844656","datavalue":{"value":"Electrical networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853151$4294EA2A-B747-421B-87B4-D58936D9457C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bc0c831139ab6eea027c47544cad3260d0e0c4df","datavalue":{"value":"Q57904545","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853151$B5816EBE-1066-404F-AA20-90FBE02DD411","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":"Q1853151$CB74D2A8-86FE-4CF5-8463-E58B55EDF40E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ec41fa5fac1f90fe31567d8b58e1dd9b795a675","datavalue":{"value":{"entity-type":"item","numeric-id":5487824,"id":"Q5487824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$3AF963D5-8BD8-45F8-8792-6FD75D4D273F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a64c66f84ef3d614c129d9701b7e0cb0d4d62295","datavalue":{"value":{"entity-type":"item","numeric-id":4223058,"id":"Q4223058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$C725E241-752B-49AE-A168-41F50284DEAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f922cddecec7bcfd257ace340a24a5f3030e8a7f","datavalue":{"value":{"entity-type":"item","numeric-id":1193886,"id":"Q1193886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$BD6B4A0C-7BAB-419E-B13A-C90DC9C34273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e838310da81f188d6518ac830c401fc2ac78699","datavalue":{"value":{"entity-type":"item","numeric-id":294802,"id":"Q294802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$70EE9F9B-22F7-4A00-9717-A8524FB77CA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e9d91cb65b5dfb256d1d68d46cc0409fda7303","datavalue":{"value":{"entity-type":"item","numeric-id":3140012,"id":"Q3140012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$93B632B1-EB93-4DE3-8BBB-BCCB968D27DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aa251e2c0514d3817d0e43c036a18d83a8e4272","datavalue":{"value":{"entity-type":"item","numeric-id":3706275,"id":"Q3706275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$43BEB1DC-BD3B-4E9C-BE55-E0FEBD67A9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a0cc081473d35a82bcf47e4cb558dc70e7bbc88","datavalue":{"value":{"entity-type":"item","numeric-id":3285875,"id":"Q3285875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853151$FC943DC9-8168-44B1-B0ED-5C5CFE8D95B4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ad135a23d2817ef3f89b81ae12cb6f3d307e1f4b","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00287-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853151$5743B259-76B7-4941-93D0-E26802BDEFBE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78bc646cf67e795545437c39618d6f5b561b410d","datavalue":{"value":"W2029198432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853151$567B3B96-19E4-4152-AF2A-B00629A9F0EB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a3520fbb0ed2651ee2722cc8c75b46830a717ed","datavalue":{"value":{"entity-type":"item","numeric-id":4418654,"id":"Q4418654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff7b7b3230412a8928a9430a8389230ba2c0b40e","datavalue":{"value":{"amount":"+0.7993906140327454","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":"Q1853151$BED43C1A-8AA5-4FE4-B4DF-ABDE56027503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5372b5a3758ce39629d7cf5d1dc11f8aa82b563e","datavalue":{"value":{"entity-type":"item","numeric-id":5487824,"id":"Q5487824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b93c807c308336c74c229acba3f9e028d432d86","datavalue":{"value":{"amount":"+0.760181188583374","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":"Q1853151$1B5421F5-6D6D-4DE6-A520-DC92953D5C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd1021118c01752a60d316da5521068d4c823fa0","datavalue":{"value":{"entity-type":"item","numeric-id":294802,"id":"Q294802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80ae98d14ef0805a3e0913f2bc02c15c490a950c","datavalue":{"value":{"amount":"+0.7563786506652832","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":"Q1853151$24B6CCC3-390F-46AF-8A95-EA2506ED1505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"309f0e14a674965af1ec9b0771fe01c196956dde","datavalue":{"value":{"entity-type":"item","numeric-id":3022753,"id":"Q3022753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18d418f8f0c38e44810c306114af68a68987da0f","datavalue":{"value":{"amount":"+0.7480445504188538","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":"Q1853151$164FF897-E1EA-4003-BD33-DA2E2F2DD318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ee508d1a95bd92d0a021ea9ee9835ce6532d048","datavalue":{"value":{"entity-type":"item","numeric-id":5501325,"id":"Q5501325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94f6fa3e79213f121500ccda42dd808b1f3d7e76","datavalue":{"value":{"amount":"+0.7459498047828674","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":"Q1853151$38AD9F5A-6889-4F1E-ACF9-7771AC86D01C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"More on random walks, electrical networks, and the harmonic \\(k\\)-server algorithm.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/More_on_random_walks,_electrical_networks,_and_the_harmonic_%5C(k%5C)-server_algorithm."}}}}}