Exceptional Paper--Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

The number of days required to clear a check drawn on a bank in city j depends on the city i in which the check is cashed. Thus, to maximize its available funds, a company that pays bills to numerous clients in various locations may find it advantageous to maintain accounts in several strategically located banks. We will discuss the problem of optimally locating bank accounts to maximize clearing times. The importance of this problem depends in part on its mathematical equivalence to the well-known uncapacitated plant location problem. We present a Lagrangian dual for obtaining an upper bound and heuristics for obtaining a lower bound on the value of an optimal solution. Our main results are analytical worst-case analyses of these bounds. In particular we show that the relative error of the dual bound and a "greedy" heuristic never exceeds [(K - 1)/K]^k < 1/e for a problem in which at most K locations are to be chosen. Two other heuristics are shown to have worst-case relative errors of at least (k - 1)/(2K - 1) < 1/2. Examples are given showing that all these bounds can be achieved. We present extensive computational results for these approximations.