Ett distribuerat nätverk modelleras av en graf med n noder (processorer) och diameter D. Vi studerar tids komplexiteten av att approximera viktade (oriktade) kortaste vägar på distribuerade nätverk med en O (log n) bandbreddsbegränsning på kanterna (standardsynkrona CONGEST-modellen). Frågan om approximationsalgoritmer bidrar till att påskynda de kortaste banorna och avståndsberäkningen (mer exakt avståndsberäkning) togs upp sedan åtminstone 2004 av Elkin (SIGACT News 2004). Det oviktade fallet med detta problem är välförståeligt, medan dess viktade motsvarighet är ett grundläggande problem när det gäller distribuerade approximationsalgoritmer och förblir allmänt öppen. Vi presenterar nya algoritmer för beräkning av både kortaste banor med en enda källa (SSSP) och alla par kortaste banor (APSP) i viktat fall. Vårt huvudsakliga resultat är en algoritm för SSSP. Tidigare resultat är den klassiska O(n)-tid Bellman-Ford algoritm och an Õ(n 1/2+1/2k +D)-tid (8k log(k+1) −1)-tillnärmning algoritm, för alla heltal k ≥ 1, som följer av resultatet av Lenzen och Patt-Shamir (STOC 2013). (Observera att Lenzen och Patt-Shamir faktiskt löser ett svårare problem, och vi använder Õ(·) för att dölja O(poly log n) term.) Vi presenterar añ O(n 1/2 D 1/4 + D)-tid (1 + o(1))-tillnärmning algoritm för SSSP. Denna algoritm är sublinjär så länge D är sublinjär, vilket ger en sublinjär tid algoritm med nästan optimal lösning. När D är liten matchar vår körtid Das Sarma et * den nedre gränsen (n 1/2 + D) för Das Sarma et * En fullständig version av detta dokument finns på http://arxiv. org/abs/1403.5171 † ), som håller även när D = (log n), upp till en poly log n faktor. Som en biprodukt av vår teknik får vi en förenklad O(n)-tid (1+o(1))-tillnärmningsalgoritm för APSP, vilket förbättrar föregående Õ(n)-tid O(1)-tillnärmningsalgoritm efter resultaten av Lenzen och Patt-Shamir. Vi visar också en matchande nedre gräns. Våra tekniker ger också en Õ (n 1/2 ) tidsalgoritm på fullt anslutna nätverk, vilket garanterar en exakt lösning för SSSP och en (2 + o(1)) ungefärlig lösning för APSP. Alla våra algoritmer förlitar sig på två nya enkla verktyg: lättviktsalgoritm för begränsad SSSP och kortast möjliga minskning av diametern via genvägar. Dessa verktyg kan vara av oberoende intresse och användbara för att utforma andra distribuerade algoritmer.
Den första approximationen gjordes av Nanongkai REF med en randomiserad algoritm för beräkning (1 + o(1) ) ungefärlig SSSP i Õ( ε n) rundor.
Distributed approximation algorithms for weighted shortest paths
{'venue': "STOC '14", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}