MPI-I-97-1-022
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: MPI-I-97-1-022.ps (117 KBytes)
URL to this document: https://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},
}