TY - GEN

T1 - Undiscretized dynamic programming

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

AU - Shah, Rahul

AU - Farach-Colton, Martin

PY - 2002

Y1 - 2002

N2 - 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 0(n2) 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(nlogn) for the Tree Location Problem and some related problems. Our approach gives a general method for solving tree dynamic programming problems.

AB - 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 0(n2) 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(nlogn) for the Tree Location Problem and some related problems. Our approach gives a general method for solving tree dynamic programming problems.

UR - http://www.scopus.com/inward/record.url?scp=33749570311&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749570311&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33749570311

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 108

EP - 115

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

Y2 - 6 January 2002 through 8 January 2002

ER -