A distributed solution for the minimum cost network flow problem is here proposed. The method uses a block version of the Gauss-Seidel algorithm in order to iteratively solve the dual problem whose structure is such that the Hessian matrix coincides with the Laplacian matrix of the corresponding graph. Thus, the updating rule turns out to be fully distributed. In order to increase the parallelism degree, a graph coloring scheme allows the clustering of nodes that reduces the sequentiality of the Gauss-Seidel technique. Numerical experiments show the effectiveness of the approach compared with methods recently presented in the literature.

A Colored Gauss-Seidel Approach for the Distributed Network Flow Problem

L Iannelli;Glielmo L
2015

Abstract

A distributed solution for the minimum cost network flow problem is here proposed. The method uses a block version of the Gauss-Seidel algorithm in order to iteratively solve the dual problem whose structure is such that the Hessian matrix coincides with the Laplacian matrix of the corresponding graph. Thus, the updating rule turns out to be fully distributed. In order to increase the parallelism degree, a graph coloring scheme allows the clustering of nodes that reduces the sequentiality of the Gauss-Seidel technique. Numerical experiments show the effectiveness of the approach compared with methods recently presented in the literature.
978-147997886-1
File in questo prodotto:
File Dimensione Formato  
1211.pdf

non disponibili

Licenza: Non specificato
Dimensione 392.12 kB
Formato Adobe PDF
392.12 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS 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/20.500.12070/10128
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact