Article ID: | iaor20012026 |
Country: | Japan |
Volume: | 43 |
Issue: | 2 |
Start Page Number: | 333 |
End Page Number: | 340 |
Publication Date: | Jun 2000 |
Journal: | Journal of the Operations Research Society of Japan |
Authors: | Nishino Hisakazu, Umezawa Masashi |
Keywords: | location, programming: dynamic |
This paper deals with a multi-facility location problem on a tree. Given the number of facilities and the tree structure, the problem is to find the optimal locations of facilities so as to maximize the service provider's gain obtained from customers accessing the nearest facility. Customers are located only at vertices of the tree. For each vertex, customers' demand function is given, which is nonincreasing piecewise linear in the distance from the vertex to the nearest facility location. We modify the algorithm proposed by Megiddo–Zemel–Hakimi, and show that it yields the exact optimum within a polynomial time.