We study approximate distributed solutions to the weighted all-pairs-shortest-paths (APSP) problem in the congest model. We obtain the following results. • A deterministic (1 + ε)-approximation to APSP with running time O(ε −2 n log n) rounds. The best previously known algorithm was randomized and slower by a Θ(log n) factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and that are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of o(n/ log n). In the relabeling model, we obtain the following results. • A randomized O(k)-approximation to APSP, for any integer k > 1, running inÕ(n 1/2+1/k + D) rounds, where D is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from O(k log k) to O(k). Also, the new algorithm uses O(log n)-bit labels, which is asymptotically optimal. • A randomized O(k)-approximation to APSP, for any integer k > 1, running in timeÕ((nD) 1/2 · n 1/k + D) and producing compact routing tables of sizeÕ(n 1/k ). The node labels consist of O(k log n) bits. This improves on the approximation ratio of Θ(k 2 ) for tables of that size achieved by the best previously known algorithm, which terminates faster, inÕ(n 1/2+1/k + D) rounds. In addition, we improve on the time complexity of the best known deterministic algorithm for distributed approximate Steiner forest.
Lenzen et al. REF showed that a (1 + )-approximate solution can be deterministically found in O( −2 · n log n) rounds.
Fast Partial Distance Estimation and Applications
PODC '15
Computer Science