Maximum Network Flow with Floating Point Arithmetic

Althaus, Ernst; Mehlhorn, Kurt

doi:10.1016/S0020-0190(98)00043-X

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Maximum Network Flow with Floating Point Arithmetic

MPS-Authors

/persons/resource/persons44003

Althaus, Ernst
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Althaus, E., & Mehlhorn, K. (1998). Maximum Network Flow with Floating Point Arithmetic. Information Processing Letters, 66(3), 109-113. doi:10.1016/S0020-0190(98)00043-X.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-372C-D

Abstract

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. Let n
and m be the number of nodes and edges of the network, respectively. For m 109
and with 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 106 and with double precision arithmetic, the relative error after
the first iteration is bounded by 10−3.