Multi-facility location problem with nonincreasing piecewise linear demand on a tree

Masashi Umezawa, Hisakazu Nishino

Research output: Contribution to journalArticle


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 (1983), and show that it yields the exact optimum within a polynomial time.

Original languageEnglish
Pages (from-to)333-340
Number of pages8
JournalJournal of the Operations Research Society of Japan
Issue number2
Publication statusPublished - Jun 2000


Cite this