title: One and two facility network design revisited
abstract: The one facility one commodity network design problem (OFOC) with nonnegative flow costs considers the problem of sending d units of flow from a source to a destination where arc capacity is purchased in batches of C units. The two facility problem (TFOC) is similar, but capacity can be purchased either in batches of C units or one unit. Flow costs are zero. These problems are known to be NP-hard. We describe an exact O(n/sup 3/3/sup n/) algorithm for these problems based on the repeated use of a bipartite matching algorithm. We also present a better lower bound of Omega (n/sup 2k*/) for an earlier Omega (n/sup 2k/) algorithm described in the literature where k = [d/C] and k* = min{k, [(n 2)/2]}. The matching algorithm is faster than this one for k >or= [(n - 2)/2]. Finally, we provide another reformulation of the problem that is quasi integral. This property could be useful in designing a modified version of the simplex method to solve the problem using a sequence of pivots with integer extreme solutions, referred to as the integral simplex method in the literature
keyphrases: two facility network design one facility one commodity network design problem nonnegative flow costs flow costs bipartite matching algorithm lower bound quasi integral pivots integral simplex method NP-hard problems exact algorithm