Location problem on trees with solid circular vertex weights
,
,
and
Article Sidebar
Full Text: 
PDF
Abstract
In this paper, the 1-median problem with the solid circular vertex weights is considered. The set operations according to the Minkowski sum are introduced. Then, optimal criterion for a vertex that is a 1-median of the trees with solid circular vertex weights is given. Based on the result, an algorithm to solve the 1-median problem with solid circular vertex weights is proposed.
Tóm tắt
Trong bài báo này, bài toán vị trí 1-median được xem xét với trọng số đỉnh hình tròn. Đầu tiên các phép toán tập hợp theo nghĩa Minkowski được giới thiệu. Sau đó, điều kiện tối ưu cho một đỉnh 1-median trên cây với trọng số đỉnh hình tròn được chỉ ra. Trên cơ sở đó, một thuật toán để giải quyết bài toán 1-median với trọng số đỉnh hình tròn sẽ được đề xuất.
Article Details
References
Agarwal, P. K., Flato, E., & Halperin, D. (2002). Polygon decomposition for efficient construction of Minkowski sums. Computational Geometry, 21(1-2), 39-61.
De Berg, M., Van Kreveld, M., Overmars, M., & Schwarzkopf, O. (1997). Computational Geometry Algorithms and Applications. Springer.
Goldman, A. J. (1971). Optimal center location in simple networks, Transportation Science, 5(2), 539-560.
Günther, C., Köbis, E., & Popovici, N. (2019). On strictly minimal elements w.r.t preorder relations in set-valued optimization, Applied Set-Valued Analysis and Optimization, 1(3), 205 – 219.
Hakimi, S. L. (1965). Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Operations research, 13(3), 462-475.
Hamacher, H. W., Labbé, M., & Nickel, S. (1999). Multicriteria network location problems with sum objectives. Networks, 33(2), 79-92.
Kalcsics, J., Nickel, S., Pozo, M. A., Puerto, J., & Rodríguez-Chía, A. M. (2014). The multicriteria p-facility median location problem on networks. European Journal of Operational Research, 235(3), 484-493.
Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics, 37(3), 513-538.
Khan, A. A., Tammer, C., & Zlinescu, C. (2015). Set-valued Optimization, An introduction with Applications. Springer. Berlin.
Pasko, A., Okunev, O., & Savchenko, V. (2003). Minkowski sums of point sets defined by inequalities. Computers & Mathematics with Applications, 45(10-11), 1479-1487.