Efficient algorithms for finding 2‐medians of a tree
- 21 September 2020
- Vol. 77 (3) , 383-402
Abstract
The p‐median problem for networks is NP‐hard, but polynomial time algorithms exist for trees (n is the number of nodes): O(pn2) by Tamir, and O(n lgp + 2 n) by Benkoczi and Bhattacharya. Goldman gave an O(n) algorithm for the 1‐median problem on trees. Mirchandani and Oudjit proved localization properties for 2‐medians on trees; these were later used to obtain an O(nlg n) bound, and, in special cases, O(n) . We present a framework that unifies all efficient algorithms for the 2‐median problem on trees. Our framework isolates the nonlinear part of the computation so that future time‐bound improvements are easily incorporated. We also introduce a method for reducing the search space, improving all known runtimes in many instances. Finally, we give a new algorithm for the case where edge lengths are positive integers. The associated time bound is O(n + D) , where D is the sum of the logarithms of edge lengths. This is O(n) if edge lengths are bounded by a constant and O(n lglg n) if they are O(lg n) . The algorithm is flexible enough to extend to noninteger edge lengths, preserving the time bound in some circumstances.Keywords
This publication has 13 references indexed in Scilit:
- Efficient algorithms for two generalized 2-median problems and the group median problem on treesTheoretical Computer Science, 2009
- The p-median problem: A survey of metaheuristic approachesEuropean Journal of Operational Research, 2007
- Solution methods for the p‐median problem: An annotated bibliographyNetworks, 2006
- A New Template for Solving p-Median Problems for Trees in Sub-quadratic Time2005
- An O(pn2) algorithm for the p-median and related problems on tree graphsOperations Research Letters, 1996
- Computing the 2‐median on tree networks in O(n lg n) timeNetworks, 1995
- Localizing 2‐medians on probabilistic and deterministic tree networksNetworks, 1980
- An Algorithmic Approach to Network Location Problems. II: Thep-MediansSIAM Journal on Applied Mathematics, 1979
- Optimal Center Location in Simple NetworksTransportation Science, 1971
- Central Facilities LocationGeographical Analysis, 1970