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

Rahul Shah; Martin Farach-Colton

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

Rahul Shah, Martin Farach-Colton

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 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.

Original language	English (US)
Title of host publication	Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Publisher	Association for Computing Machinery
Pages	108-115
Number of pages	8
ISBN (Electronic)	089871513X
State	Published - 2002
Event	13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States Duration: Jan 6 2002 → Jan 8 2002

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	06-08-January-2002

Other

Other	13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/Territory	United States
City	San Francisco
Period	1/6/02 → 1/8/02

ASJC Scopus subject areas

Software
General Mathematics

Cite this

Shah, R., & Farach-Colton, M. (2002). Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 (pp. 108-115). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002). Association for Computing Machinery.

Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. / Shah, Rahul; Farach-Colton, Martin.
Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery, 2002. p. 108-115 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Shah, R & Farach-Colton, M 2002, Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 06-08-January-2002, Association for Computing Machinery, pp. 108-115, 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, San Francisco, United States, 1/6/02.

@inproceedings{e8f9d81dd2524a9b912b4e1fd02de8e2,

title = "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 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.",

author = "Rahul Shah and Martin Farach-Colton",

year = "2002",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "108--115",

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

note = "13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 ; Conference date: 06-01-2002 Through 08-01-2002",

}

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 -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this