Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees

ABSTRACT

In the Uncapacitated Facility Location (UFL) problem, there is a fixed cost for opening a facility, and some distance matrix d that determines the cost of distributing commodities from any facility i to any consumer j. The problem is NP-hard in general and when d consists of a distance metric in a graph [7, 12]. However, for the case where the commodity transportation costs are given by path lengths in a tree, an O(n²) dynamic programming algorithm was given by [4, 7]. We improve this dynamic programming algorithm by using the geometry of piecewise linear functions and fast merging of the binary search trees used to store these functions. We achieve the complexity bound of O(n log n) for the Tree Location Problem and some related problems. Our approach gives a general method for solving tree dynamic programming problems.

REFERENCES

• 1: A. Tamir, "An O(pn2) algorithm for the p-median and related problems on tree graphs", Operations Research Letters, 19:59-94, 1996.
• 2: Stefan Langerman , Sachin Lodha , Rahul Shah, Algorithms for Efficient Filtering in Content-Based Multicast, Proceedings of the 9th Annual European Symposium on Algorithms, p.428-439, August 28-31, 2001
• 3: A. Kolen, "Solving covering problems and the uncapacitated plant location problem on trees", European Journal of Operations Research, 12, 266-278, 1983.
• 4: D. Shaw, "A unified limited column generation approach for facility location problems on trees", Annuals of Operations Research, 87, 363-382, 1999.
• 5: R. Hassin and A. Tamir, "Improved complexity bounds for location problems on the real line", Operations Research Letters, 10, 395-402, 1991.
• 6: A. Tamir and T. Lowe, "The generalized p-forest problem on a tree network", Networks 22, 217-230, 1992.
• 7: G. Cornuejols, G. L. Nemhauser and L. A. Wosley, "The uncapacitated facility location problem", in P. B. Mirchandani and R. L. Francis(eds), Discrete Location Theory, Wiley, New York, 1990, pp. 119-171.
• 8: Mark R. Brown , Robert E. Tarjan, A Fast Merging Algorithm, Journal of the ACM (JACM), v.26 n.2, p.211-226, April 1979 [doi>10.1145/322123.322127]
• 9: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 10: G. Adel'son-Vel'skii and Y. Landis, "An algorithm for the organization of information", Dokl. Akad. Nauk SSSR 146, 263-266, (in Russian) English translation in Soviet Math. Dokl., 3-1962, pp1259-1262.
• 11: Clark Allan Crane, Linear lists and priority queues as balanced binary trees, 1972
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979