SPECIALLY STRUCTURED UNCAPACITATED FACILITY LOCATION-PROBLEMS

This paper considers a specially structured uncapacitated facility loc ation problem. We show that several problems, including certain tool s election problems, substitutable inventory problems, supplier sourcing problems, discrete lot sizing problems, and capacity expansion proble ms, can be formulated as instances of the problem. We also show that t he problem with m facilities and n customers can be solved in O(mn), a s a shortest path problem on a directed graph.