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]

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

[2]

Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973

[3]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355

[4]

M. R. S. Kulenović, J. Marcotte, O. Merino. Properties of basins of attraction for planar discrete cooperative maps. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2721-2737. doi: 10.3934/dcdsb.2020202

[5]

Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[6]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[7]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[8]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[9]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623

[10]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463

[11]

Alexey Yulin, Alan Champneys. Snake-to-isola transition and moving solitons via symmetry-breaking in discrete optical cavities. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1341-1357. doi: 10.3934/dcdss.2011.4.1341

[12]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195

[13]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401

[14]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[15]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

[16]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205

[17]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453

[18]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090

[19]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[20]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]