# American Institute of Mathematical Sciences

January  2012, 8(1): 41-49. doi: 10.3934/jimo.2012.8.41

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

 1 Faculty of Management and Administration, Macau University of Science and Technology, Avenida Wai Long, Taipa, Macau SAR, China 2 Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China 3 Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong SAR, China

Received  January 2011 Revised  May 2011 Published  November 2011

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.
Citation: Huajun Tang, T. C. Edwin Cheng, Chi To Ng. A note on the subtree ordered median problem in networks based on nestedness property. Journal of Industrial & Management Optimization, 2012, 8 (1) : 41-49. doi: 10.3934/jimo.2012.8.41
##### References:
 [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [4] S. Nickel, and J. Puerto, "Location Theory: A Unified Approach," 1st edition, Springer-Verlag, Berlin, 2005. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar

show all references

##### References:
 [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [4] S. Nickel, and J. Puerto, "Location Theory: A Unified Approach," 1st edition, Springer-Verlag, Berlin, 2005. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar
 [1] Veena Goswami, Gopinath Panda. Optimal information policy in discrete-time queues with strategic customers. Journal of Industrial & Management Optimization, 2019, 15 (2) : 689-703. doi: 10.3934/jimo.2018065 [2] Gopinath Panda, Veena Goswami. Effect of information on the strategic behavior of customers in a discrete-time bulk service queue. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1369-1388. doi: 10.3934/jimo.2019007 [3] Ganfu Wang, Xingzheng Ai, Chen Zheng, Li Zhong. Strategic inventory under suppliers competition. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2159-2173. doi: 10.3934/jimo.2019048 [4] Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006 [5] Nickolas J. Michelacakis. Strategic delegation effects on Cournot and Stackelberg competition. Journal of Dynamics & Games, 2018, 5 (3) : 231-242. doi: 10.3934/jdg.2018015 [6] Gang Chen, Zaiming Liu, Jingchuan Zhang. Analysis of strategic customer behavior in fuzzy queueing systems. Journal of Industrial & Management Optimization, 2020, 16 (1) : 371-386. doi: 10.3934/jimo.2018157 [7] Misha Perepelitsa. A model of cultural evolution in the context of strategic conflict. Kinetic & Related Models, 2021, 14 (3) : 523-539. doi: 10.3934/krm.2021014 [8] Guodong Yi, Xiaohong Chen, Chunqiao Tan. Optimal pricing of perishable products with replenishment policy in the presence of strategic consumers. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1579-1597. doi: 10.3934/jimo.2018112 [9] Natalia Kudryashova. Strategic games in a competitive market: Feedback from the users' environment. Conference Publications, 2015, 2015 (special) : 745-753. doi: 10.3934/proc.2015.0745 [10] Marta Faias, Emma Moreno-García, Myrna Wooders. A strategic market game approach for the private provision of public goods. Journal of Dynamics & Games, 2014, 1 (2) : 283-298. doi: 10.3934/jdg.2014.1.283 [11] Sheng Zhu, Jinting Wang. Strategic behavior and optimal strategies in an M/G/1 queue with Bernoulli vacations. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1297-1322. doi: 10.3934/jimo.2018008 [12] Ke Sun, Jinting Wang, Zhe George Zhang. Strategic joining in a single-server retrial queue with batch service. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3309-3332. doi: 10.3934/jimo.2020120 [13] Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108 [14] Dengfeng Sun, Issam S. Strub, Alexandre M. Bayen. Comparison of the performance of four Eulerian network flow models for strategic air traffic management. Networks & Heterogeneous Media, 2007, 2 (4) : 569-595. doi: 10.3934/nhm.2007.2.569 [15] Ruopeng Wang, Jinting Wang, Chang Sun. Optimal pricing and inventory management for a loss averse firm when facing strategic customers. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1521-1544. doi: 10.3934/jimo.2018019 [16] Uri M. Ascher. Discrete processes and their continuous limits. Journal of Dynamics & Games, 2020, 7 (2) : 123-140. doi: 10.3934/jdg.2020008 [17] Saber Shiripour, Nezam Mahdavi-Amiri. Median location problem with two probabilistic line barriers: Extending the Hook and Jeeves algorithm. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021128 [18] Jean-Bernard Baillon, Guillaume Carlier. From discrete to continuous Wardrop equilibria. Networks & Heterogeneous Media, 2012, 7 (2) : 219-241. doi: 10.3934/nhm.2012.7.219 [19] Ivica Martinjak, Mario-Osvin Pavčević. Symmetric designs possessing tactical decompositions. Advances in Mathematics of Communications, 2011, 5 (2) : 199-208. doi: 10.3934/amc.2011.5.199 [20] André Nachbin. Discrete and continuous random water wave dynamics. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1603-1633. doi: 10.3934/dcds.2010.28.1603

2020 Impact Factor: 1.801