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

Huajun Tang; T. C. Edwin Cheng; Chi To Ng

doi:10.3934/jimo.2012.8.41

Article Contents

2012, Volume 8, Issue 1: 41-49. Doi: 10.3934/jimo.2012.8.41

This issue Previous Article Optimal inventory control with fixed ordering cost for selling by internet auctions Next Article A penalty method for generalized Nash equilibrium problems

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
2.
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
3.
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong SAR

Received: January 2011

Revised: May 2011

Published: January 2012

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90-107, 90-63; Secondary: 90B18, 90B19.

Citation:

Related Papers

Cited by

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.
[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," 1^st 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.