# MPI-I-97-1-022

## Maximum network flow with floating point arithmetic

### Althaus, Ernst and Mehlhorn, Kurt

**MPI-I-97-1-022**. October** **1997, 5 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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}$.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 117 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-022

**BibTeX**
`@TECHREPORT{``AlthausMehlhorn97``,`

` 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},`

`}`