document: One and two facility network design revisited The one facility one commodity network design problem -LRB- OFOC -RRB- 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 -LRB- TFOC -RRB- 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 -LRB- n/sup 3/3/sup n / -RRB- algorithm for these problems based on the repeated use of a bipartite matching algorithm . We also present a better lower bound of Omega -LRB- n/sup 2k * / -RRB- for an earlier Omega -LRB- n/sup 2k / -RRB- algorithm described in the literature where k = -LSB- d/C -RSB- and k * = min -LCB- k , -LSB- -LRB- n 2 -RRB- / 2 -RSB- -RCB- . The matching algorithm is faster than this one for k > or = -LSB- -LRB- n - 2 -RRB- / 2 -RSB- . 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
doc_bio_tags: O O B I I I O O B I I I I I I O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O B I I O O O