Becker, Ruben ;
Karrenbauer, Andreas ;
Krinninger, Sebastian ;
Lenzen, Christoph
NearOptimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Abstract
We present a method for solving the shortest transshipment problem  also known as uncapacitated minimum cost flow  up to a multiplicative error of (1 + epsilon) in undirected graphs with nonnegative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes epsilon^(3) polylog(n) iterations, and in each iteration it needs to solve an instance of the transshipment problem up to a multiplicative error of polylog(n), where n is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a careful whitebox analysis, we can further extend the method to finding approximate solutions for the singlesource shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results:
(1) Broadcast CONGEST model: (1 + epsilon)approximate SSSP using ~O((sqrt(n) + D) epsilon^(O(1))) rounds, where D is the (hop) diameter of the network.
(2) Broadcast congested clique model: (1 + epsilon)approximate shortest transshipment and SSSP using ~O(epsilon^(O(1))) rounds.
(3) Multipass streaming model: (1 + epsilon)approximate shortest transshipment and SSSP using ~O(n) space and ~O(epsilon^(O(1))) passes.
The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume nonnegative integer edge weights that are polynomially bounded in n; for general nonnegative weights, running times scale with the logarithm of the maximum ratio between nonzero weights. In case of asymmetric costs for traversing an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.
BibTeX  Entry
@InProceedings{becker_et_al:LIPIcs:2017:8003,
author = {Ruben Becker and Andreas Karrenbauer and Sebastian Krinninger and Christoph Lenzen},
title = {{NearOptimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {7:17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8003},
URN = {urn:nbn:de:0030drops80031},
doi = {10.4230/LIPIcs.DISC.2017.7},
annote = {Keywords: Shortest Paths, Shortest Transshipment, Undirected Mincost Flow, Gradient Descent, Spanner}
}
2017
Keywords: 

Shortest Paths, Shortest Transshipment, Undirected Mincost Flow, Gradient Descent, Spanner 
Seminar: 

31st International Symposium on Distributed Computing (DISC 2017)

Issue date: 

2017 
Date of publication: 

2017 