Vi studerar ungefärliga distribuerade lösningar till de viktade alla-par-kortaste-paterna (APSP) problem i trängselmodellen. Vi får följande resultat. • En deterministisk (1 + ε)-uppskattning till APSP med körtid O(ε −2 n log n) rundor. Den mest kända algoritmen randomiserades och avtog långsammare med hjälp av en (log n) faktor. I många fall, routing system innebär ommärkning, dvs. att tilldela nya namn till noder och som används i avstånd och routing frågor. Det är känt att ommärkning är nödvändig för att uppnå körtider för o( n/ log n). I ommärkningsmodellen får vi följande resultat. • En randomiserad O(k)-uppskattning till APSP, för alla heltal k > 1, kör i Õ(n 1/2+1/k + D) rundor, där D är nätverkets humlediameter. Denna algoritm förenklar det mest kända resultatet och minskar dess approximationsförhållande från O(k log k) till O(k). Dessutom använder den nya algoritmen O(log n)-bitars etiketter, vilket är asymptotiskt optimalt. • En randomiserad O(k)- approximation till APSP, för alla heltal k > 1, körs i tid Õ(nD) 1/2 · n 1/k + D) och producerar kompakta routing tabeller av storlek Õ(n 1/k ). Nodetiketterna består av bitar av O(k log n). Detta förbättrar approximationsförhållandet mellan (k 2 ) för tabeller av den storleken som uppnås av de bästa tidigare kända algoritmen, som slutar snabbare, i Õ(n 1/2+1/k + D) rundor. Dessutom förbättrar vi tids komplexiteten hos den mest kända deterministiska algoritmen för distribuerad ungefärlig Steinerskog.
Lenzen m.fl. REF visade att en (1 + ) ungefärlig lösning kan deterministiskt hittas i O( −2 · n log n) rundor.
Fast Partial Distance Estimation and Applications
{'venue': "PODC '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}