We address the problem of modifying vertex weights of a tree in such an optimal way that a given facility (vertex) becomes a 1-median in the modified tree. Here, each modifying cost receive any value within an interval. As the costs are not exactly known, we apply the concept of absolute robust and minmax regret criteria to measure the cost functions. We first consider the absolute robust inverse 1-median problem with sum objective function. The duality of the problem helps to know the convexity of the induced univariate minimization problem. Based on the convexity, an O(n log2 n) time algorithm is developed, where n is the number of vertices on the underlying tree. We also apply the minmax regret criteria to the uncertain inverse 1-median problem with Chebyshev norm and bottleneck Hamming distance. It is shown that in the optimal solution there exists exactly one cost coefficient attaining the upper bound and the others attaining their lower bounds. Hence, we develop strongly polynomial-time algorithms for the problems based on this special property.
Tạp chí khoa học Trường Đại học Cần Thơ
Lầu 4, Nhà Điều Hành, Khu II, đường 3/2, P. Xuân Khánh, Q. Ninh Kiều, TP. Cần Thơ
Điện thoại: (0292) 3 872 157; Email: tapchidhct@ctu.edu.vn
Chương trình chạy tốt nhất trên trình duyệt IE 9+ & FF 16+, độ phân giải màn hình 1024x768 trở lên