We present a method for solving the shortest transshipment problem-also known as uncapacitated minimum cost flow-up to a multiplicative error of 1 + ϵ in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes ϵ-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 white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results: 1. Broadcast CONGEST model: (1+")-approximate SSSP using Õ((√ n+D) · ϵ-O(1)) rounds, 1 where D is the (hop) diameter of the network. 2. Broadcast congested clique model: (1+ϵ)-approximate shortest transshipment and SSSP using Õ (ϵ-O(1)) rounds. 3. Multipass streaming model: (1+ϵ)-approximate shortest transshipment and SSSP using Õ (n) space and Õ(ϵ-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 non-negative integer edge weights that are polynomially bounded in n; for general nonnegative weights, running times scale with the logarithm of the maximum ratio between non-zero 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.

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

Becker R.;
2017-01-01

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 + ϵ in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes ϵ-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 white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results: 1. Broadcast CONGEST model: (1+")-approximate SSSP using Õ((√ n+D) · ϵ-O(1)) rounds, 1 where D is the (hop) diameter of the network. 2. Broadcast congested clique model: (1+ϵ)-approximate shortest transshipment and SSSP using Õ (ϵ-O(1)) rounds. 3. Multipass streaming model: (1+ϵ)-approximate shortest transshipment and SSSP using Õ (n) space and Õ(ϵ-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 non-negative integer edge weights that are polynomially bounded in n; for general nonnegative weights, running times scale with the logarithm of the maximum ratio between non-zero 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.
2017
Leibniz International Proceedings in Informatics, LIPIcs
File in questo prodotto:
File Dimensione Formato  
LIPIcs-DISC-2017-7.pdf

accesso aperto

Tipologia: Versione dell'editore
Licenza: Copyright dell'editore
Dimensione 614.13 kB
Formato Adobe PDF
614.13 kB Adobe PDF Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/5029569
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 55
  • ???jsp.display-item.citation.isi??? ND
social impact