Vi studerar datorer alla-par kortaste vägar (APSP) på distribuerade nätverk (CONGEST-modellen). Målet är att varje nod i det (viktade) nätverket ska känna till avståndet från varje annan nod med hjälp av kommunikation. Problemet medger (1+o(1))-uppskattning Õ(n)-tidsalgoritmer [2], [3], som matchas med en (n)-tid lägre gränser [3], [4], [5] 1. Ingen nedre gräns eller o(m) övre gräns var känd för exakt beräkning. I detta dokument presenterar vi en Õ(n 5/4 )-tids randomiserad (Las Vegas) algoritm för exakt viktad APSP; detta ger den första förbättringen jämfört med den naiva O(m)-tidsalgoritmen när nätverket inte är så sparsamt. Vårt resultat håller också för fallet där kantvikter är asymmetriska (alias. Det riktade fallet där kommunikationen är dubbelriktad. Våra tekniker ger också en Õ(n 3/4 k 1/2 + n)-tidsalgoritm för ksource kortaste banor problem där vi vill att varje nod ska veta avstånd från k källor; detta förbättrar Elkin nyligen bundna [6] när k = på 1/4 ). Vi uppnår ovanstående resultat genom att utveckla distribuerade algoritmer ovanpå den klassiska skaltekniken, som vi tror används för första gången för distribuerade kortaste vägar beräkning. En ny algoritm som kan vara av oberoende intresse är för den omvända r-sänk kortaste vägar problem, där vi vill att varje r sänkor att veta sina avstånd från alla andra noder, med tanke på att varje nod redan vet sitt avstånd till varje diskbänk. Vi visar en Õ(n ε r)-tidsalgoritm för detta problem. En annan ny algoritm kallas kortdistansförlängning, där vi visar att kunskaperna om avstånd kan "utökas" för ytterligare h humle. För detta använder vi viktavrundning för att införa små additiva fel som kan fastställas senare. Anmärkning: Oberoende av vårt resultat konstaterade Elkin nyligen [6] att samma tekniker från en tidigare version av samma tidning (https://arxiv.org/abs/1703.01939v1) ledde till en O(n 5/3 log 2/3 n)-tidsalgoritm.
Den nuvarande bäst bundet för den viktade k-SSP problem beror på Huang et al s Ref randomiserade algoritm som körs i Õ(n 3/4 ·k 1/2 +n) rundor.
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^{5/4}) Rounds
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}