Premium
Distance‐constrained multifacility minimax location problems on tree networks
Author(s) -
Erkut E.,
Francis R. L.,
Tamir A.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220104
Subject(s) - minimax , tree (set theory) , representation (politics) , tree network , order (exchange) , mathematical optimization , polynomial , computer science , facility location problem , mathematics , time complexity , algorithm , theoretical computer science , combinatorics , mathematical analysis , finance , politics , political science , law , economics
We consider the problem of locating new facilities with respect to existing facilities on a tree network. The objective is to minimize the maximum of the weighted distances between existing and new facilities and between pairs of new facilities. There are upper bounds on the distances between pairs of new facilities and between new and existing facilities. We give a polynomial order, binary search algorithm, based on rational representation of data. We also present a strongly polynomial order algorithm employing a parameteric approach and exploiting parallelism.