A linear time algorithm for the p -maxian problem on trees with distance constraint
- PDF / 515,753 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 189 Views
A linear time algorithm for the p-maxian problem on trees with distance constraint Trung Kien Nguyen1
· Nguyen Thanh Hung1 · Huong Nguyen-Thu1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
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. Keywords Location problem · Maxian problem · Tree · Convex Mathematics Subject Classification 90B10 · 90B80 · 90C27
1 Introduction Location analysis addresses the problem of planning new optimal facilities (servers) on a system of existing facilities (customers). The median and center location problems are the two most popular classes in the classical location science. The median problem is to find one or several facilities to minimize the total weighted distance from customers
This research is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 101.01-2019.325.
B
Trung Kien Nguyen [email protected] Nguyen Thanh Hung [email protected] Huong Nguyen-Thu [email protected]
1
Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam
123
Journal of Combinatorial Optimization
to the servers. Besides, the center problem is to locate servers such that the maximum weighted distance from customers to them is minimized. For algorithmic approaches concerning the median and center location problem, we refer to Kariv and Hakimi (1979a, b); Drezner and Hamacher (2002), and references therein. While the general location problem with multi-facilities is NP-hard, special cases with polynomial-time solvability are interesting. Goldman (1971) showed that the 1-median problem on trees can be solved in linear time. Moreover, the 2-median problem on trees can be solved in O(n log n) time by Gavish and Sridhar (1995). Generally, the p-median problem on trees can be also solved in polynomial time; see Tamir (1996). For the sake of center function, the 1-center problem on trees can be solved in linear time; see Handler (1973). The p-center problem on trees can be also solved in O(n log n) time by Wang and Zhang (2002). Besides the classical location problem, researchers extended the topic in order to make it meaningful in modeling practical problems. In what follows, we briefly introduce some extensions of location theory. Universal approach for location problem has been developed under the sight of ordered median function. To apply this function, we can model a class of location problems in a u
Data Loading...
