Article Contents
Article Contents

# A note on the subtree ordered median problem in networks based on nestedness property

• The nestedness property has become an increasingly important means for devising efficient algorithms for network location problems. In this paper we prove that the nestedness property holds for the tactical continuous, and strategic discrete and continuous subtree location problems in a tree network with the ordered median objective, where the $\lambda$-weights take at most two different values. These results extend some existing results in the literature. With these nestedness results, we solve the problems in polynomial time. Finally we pose an open problem on identifying the nestedness property for the $(k_1,k_2)$-trimmed problem.
Mathematics Subject Classification: Primary: 90-107, 90-63; Secondary: 90B18, 90B19.

 Citation:

•  [1] J. N. Hooker, R. S. Garfinkel and C. K. Chen, Finite dominating sets for network location problems, Operations Research, 39 (1991), 100-118.doi: 10.1287/opre.39.1.100. [2] J. Kalcsics, S. Nickel and J. Puerto, Multi-facility ordered median problems: A further analysis, Networks, 41 (2003), 1-12.doi: 10.1002/net.10053. [3] E. Minieka, The optimal location of a path or tree in a tree network, Networks, 15 (1985), 309-321.doi: 10.1002/net.3230150304. [4] S. Nickel, and J. Puerto, "Location Theory: A Unified Approach," 1st edition, Springer-Verlag, Berlin, 2005. [5] W. Ogryczak and A. Tamir, Minimizing the sum of $k$ largest functions in linear time, Information Processing Letters, 85 (2003), 117-122.doi: 10.1016/S0020-0190(02)00370-8. [6] J. Puerto, and A. Tamir, Locating tree-shaped facilities using the ordered median objective, Mathematical Programming, 102 (2005), 313-338.doi: 10.1007/s10107-004-0547-2. [7] A. Tamir, J. Puerto and D. Pérez-Brito, The centdian subtree on tree networks, Discrete Applied Mathematics, 18 (2002), 263-278.doi: 10.1016/S0166-218X(01)00199-8. [8] H. J. Tang, T. C. E. Cheng and C. T. Ng, Finite dominating sets for the multi-facility ordered median problem in networks and algorithmic applications, Computers & Industrial Engineering, 57 (2009), 707-712.doi: 10.1016/j.cie.2009.01.015. [9] H. J. Tang, T. C. E. Cheng and C. T. Ng, Multi-facility ordered median problems in directed networks, Journal of Systems Science and Complexity, 24 (2011), 61-67.doi: 10.1007/s11424-011-9327-2. [10] P. M. Vaidya, An algorithm for linear programming which requires $O((m+n)n^2+(m+n)^{1.5}nL)$ arithmetic operations, Mathematical Programming, 47 (1990), 175-201.doi: 10.1007/BF01580859. [11] B.-F. Wang, Efficient parallel algorithms for optimally locating a path and a tree of a specified length in a weighted tree network, Journal of Algorithms, 34 (2000), 90-108.doi: 10.1006/jagm.1999.1020.