MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Maximum network flow with floating point arithmetic

Althaus, Ernst and Mehlhorn, Kurt

October 1997, 5 pages.

Status: available - back from printing

We discuss the implementation of network flow algorithms in floating point arithmetic. We give an example to illustrate the difficulties that may arise when floating point arithmetic is used without care. We describe an iterative improvement scheme that can be put around any network flow algorithm for integer capacities. The scheme carefully scales the capacities such that all integers arising can be handled exactly using floating point arithmetic. For $m \le 10^9$ and double precision floating point arithmetic the number of iterations is always bounded by three and the relative error in the flow value is at most $2^{-19}$. For $m \le 10^6$ and double precision arithmetic the relative error after the first iteration is bounded by $10^{-3}$.

  • Attachement: (117 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Althaus, Ernst and Mehlhorn, Kurt},
  TITLE = {Maximum network flow with floating point arithmetic},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-022},
  MONTH = {October},
  YEAR = {1997},
  ISSN = {0946-011X},