The typical median subtree problem on trees is to locate a (continuous) tree-shaped facility (the leaves of this facility are not necessary vertices) with a specified length to minimize the total weighted distance of all vertices to the new facility. In this paper, each vertex weight can be any value within an interval and the total deviation of weights is limited within a threshold. We want to find a subtree that minimizes the median function in the worst-case scenario. This is the so-called minmax robust median subtree problem on trees. In order to solve the problem, we first consider the minmax robust 1-median problem on trees and solve the problem in O(n log n) time. Then, the nestedness property is coined, i.e., any optimal subtree must contain a robust 1-median in the tree. Based on this property, we develop a greedy algorithm that solves the corresponding problem in O(n^4) time.
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