Given a tree network on which each node has its own demand and also stands for a candidate location of a potential facility, such as plant or warehouse, the p-median problem on the network (PMPOT) is to select less than or equal to p number of facility locations so that the whole demand on a node is satisfied from only one facility and the total demand occurred on the network can be satisfied from those facilities with the minimum total cost, where the total cost is the sum of transportation costs and the fixed costs and the fixed costs of establishing facilities. Tamir developed an O(p n2) algorithm for PMPOT which is known to be the best algorithm in terms of the time complexity, where n is the number of nodes in the network, but he didn't make any comments or explanation about implementation details for finding the optimal solution. In contrast to Tamir's work, Kariv and Hakimi developed O(p2 n2) algorithm for PMPOT and presented O(n2) algorithm for finding the optimal solution in detail. In this paper, we not only develop another O(p n2) dynamic programming algorithm for PMPOT that is competitive to Tamir's algorithm in terms of the time complexity, but also present O(n) algorithm that is more efficient than Kariv and Hakimi's algorithm in finding the optimal solution. Finally, we implement our algorithm on a set of randomly generated problems and report the computational results.
