×

Maximum network flow with floating point arithmetic. (English) Zbl 1078.68670

Summary: 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\leq 10^9\) 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\leq 10^6\) and with double precision arithmetic, the relative error after the first iteration is bounded by \(10^{-3}\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
90C35 Programming involving graphs or networks

Software:

LEDA
Full Text: DOI

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum-flow problem, J. ACM, 35, 921-940 (1988) · Zbl 0661.90031
[3] IEEE standard 754-1985 for binary floating-point arithmetic, SIGPLAN Notices, 2, 9-25 (1987)
[4] Mehlhorn, K.; Näher, S., Leda, a platform for combinatorial and geometric computing, Comm. ACM, 38, 96-102 (1995)
[5] Mehlhorn, K.; Näher, S.; Uhrig, C., Technical report, (The LEDA User Manual (1997), Max-Planck-Institut für Informatik), (Version R3.5)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.