Abstract
This paper concerns the p-maxian problem on trees with an upper bound on the distance of new facilities. We first consider the case \(p = 2\) and show that the optimal objective is obtained if the constraint holds with equality. By this result, we further explore the characteristic of the optimal solution, which helps to develop a linear time algorithm to solve the constrained 2-maxian problem. The result can be extended to the constrained p-maxian on trees based on the nestedness property. We also discuss the constrained p-maxian problem on trees in relation to the unconstrained p-maxian problem and the 1-maxian problem on the underlying tree.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alizadeh B, Burkard RE (2011) Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees. Networks 58(3):190–200
Averbakh I, Berman O (2000) Minmax regret median location on a network under uncertainty: INFORMS. J Comput 12(2):104–110
Bai C, Kang L, Shan E (2018) The connected \(p\)-center problem on cactus graphs. Theor Comput Sci 749:59–65
Bhattacharya B, Kameda T, Song Z (2014) A linear time algorithm for computing minmax regret 1-median on a tree network. Algorithmica 70:2–21
Burkard RE, Fathali J, Kakhki HT (2007) The \(p\)-maxian problem on a tree. Oper Res Lett 35(3):331–335
Burkard RE, Pleschiutschnig C, Zhang JZ (2004) Inverse median problems. Discrete Optim 1(1):23–39
Chang SC, Yen WCK, Wang YL, Liu JJ (2016) The connected \(p\)-median problem on block graphs. Optim Lett 10:1191–1201
Cheng YK, Kang L (2010) The \(p\)-maxian problem on interval graphs. Discrete Appl Math 158(18):1986–1993
Drezner Z, Hamacher HW (2002) Facility location—applications and theory. Springer, Berlin
Gavish B, Sridhar S (1995) Computing the 2-median on tree networks in \(O(n \log n)\) time. Networks 26(4):305
Goldman AJ (1971) Optimal center location in simple networks. Transport Sci 5(2):539–560
Handler GY (1973) Minimax location of a facility in an undirected tree networks. Transp Sci 7(3):287–293
Kalcsics J, Nickel S, Puerto J, Tamir A (2002) Algorithmic results for ordered median problems. Oper Res Lett 30(3):149–158
Kang L, Cheng Y (2010) The \(p\)-maxian problem on block graphs. J Comb Opt 20:131–141
Kang L, Shang E, Bai C, Nguyen K (2014) The 2-maxian problem on cactus graphs. Discrete Opt 13:16–22
Kang L, Zhou J, Shan E (2018) Algorithms for connected \(p\)-centdian problem on block graphs. J Comb Opt 36:252–263
Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems, I. p-centers SIAM J Appl Math 37(3):513–538
Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems, II. p-medians SIAM J Appl Math 37(3):539–560
Kazda A, Caves R (2000) Airport Design and Operation, 3rd edn. Emerald Group Publishing Limited, Bingley
Krarup J, Pisinger D, Plastria F (2002) Discrete location problems with push-pull objectives. Discrete Appl Math 123(1–3):363–378
Mesa JA, Boffey TB (1996) A review of extensive facility location in networks. Eur J Oper Res 95(3):592–603
Nguyen KT (2016) Inverse 1-median problem on block graphs with variable vertex weights. J Optim Theory Appl 168:944–957
Nguyen KT, Chassein A (2015) The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance. Eur J Oper Res 247(3):774–781
Nickel S, Puerto J (2005) Location Theory—A unified approach. Springer, Berlin
Pham VH, Nguyen KT, Le TT (2020) Inverse stable point problem on trees under an extension of Chebyshev norm and Bottleneck Hamming distance. Optim Methods Softw. https://doi.org/10.1080/10556788.2020.1713778
Puerto J, Ricca F, Scozzari A (2018) Extensive facility location problems on networks: an updated review. TOP 26(2):187–226
Tamir A (1996) An \(O(pn^2)\) Algorithm for the \(p\)-median and related problems on tree graphs. Oper Res Lett 19(2):59–64
Tamir A (1991) Obnoxious facility location on graphs. SIAM J Discrete Math 4(4):550–567
Ting SS (1984) A linear-time algorithm for maxisum facility location on tree networks. Transp Sci 18(1):76–84
Wang, H., Zhang, J.: An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees. Symposium on Computational Geometry, 2017
Yen WCK (2012) The connected \(p\)-center problem on block graphs with forbidden vertices. Theor Comput Sci 47:13–24
Acknowledgements
The authors would like to acknowledge anonymous referees for their valuable comments which help to improve the paper significantly.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 101.01-2019.325.
Rights and permissions
About this article
Cite this article
Nguyen, T.K., Hung, N.T. & Nguyen-Thu, H. A linear time algorithm for the p-maxian problem on trees with distance constraint. J Comb Optim 40, 1030–1043 (2020). https://doi.org/10.1007/s10878-020-00650-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-020-00650-9