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. 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. 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. doi: 10.1002/net.3230150304. Google Scholar

[4]

S. Nickel, and J. Puerto, "Location Theory: A Unified Approach,", 1st edition, (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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1002/net.3230150304. Google Scholar

[4]

S. Nickel, and J. Puerto, "Location Theory: A Unified Approach,", 1st edition, (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. 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. 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. 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. 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. 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. 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. 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]

Ganfu Wang, Xingzheng Ai, Chen Zheng, Li Zhong. Strategic inventory with competing suppliers. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019048

[3]

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, 2017, 13 (5) : 1-20. doi: 10.3934/jimo.2019007

[4]

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

[5]

Gang Chen, Zaiming Liu, Jingchuan Zhang. Analysis of strategic customer behavior in fuzzy queueing systems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2018157

[6]

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

[7]

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

[8]

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

[9]

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

[10]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019108

[11]

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

[12]

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

[13]

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

[14]

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

[15]

André Nachbin. Discrete and continuous random water wave dynamics. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1603-1633. doi: 10.3934/dcds.2010.28.1603

[16]

Yuanyuan Feng, Lei Li, Jian-Guo Liu, Xiaoqian Xu. Continuous and discrete one dimensional autonomous fractional ODEs. Discrete & Continuous Dynamical Systems - B, 2018, 23 (8) : 3109-3135. doi: 10.3934/dcdsb.2017210

[17]

Viviana Alejandra Díaz, David Martín de Diego. Generalized variational calculus for continuous and discrete mechanical systems. Journal of Geometric Mechanics, 2018, 10 (4) : 373-410. doi: 10.3934/jgm.2018014

[18]

Muriel Boulakia. Quantification of the unique continuation property for the nonstationary Stokes problem. Mathematical Control & Related Fields, 2016, 6 (1) : 27-52. doi: 10.3934/mcrf.2016.6.27

[19]

Alexander J. Zaslavski. The turnpike property of discrete-time control problems arising in economic dynamics. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 861-880. doi: 10.3934/dcdsb.2005.5.861

[20]

Jeong-Yup Lee, Boris Solomyak. Pisot family self-affine tilings, discrete spectrum, and the Meyer property. Discrete & Continuous Dynamical Systems - A, 2012, 32 (3) : 935-959. doi: 10.3934/dcds.2012.32.935

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]