MAXIMUM NETWORK FLOW WITH FLOATING-POINT ARITHMETIC

We discuss the implementation of network flow algorithms in floating p oint arithmetic. We give an example to illustrate the difficulties tha t may arise when floating point arithmetic is used without care. We de scribe an iterative improvement scheme that can be put around any netw ork 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 ii and rn be the number of nodes and edges of the network, respectively. For m less than or equal to 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 less than or equal to 10(6) and wi th double precision arithmetic, the relative error after the first ite ration is bounded by 10(-3). (C) 1998 Elsevier Science B.V. All rights reserved.