In this paper, we propose a unified approach to solving the inverse 1-median problem on trees under both the sum and max objectives by using the ordered median function. For the problem under the k-centrum cost function, we investigate the structure of an optimal solution and transform the problem into a univariate optimization problem where the parameter equals the k largest cost. We take advantage of the convexity of the objective function to efficiently find theoptimal solution in O(n log n) time, where n is the number of vertices in the tree. For the problem under the centdian cost function, we parameterize it based on the maximum cost item and prove that the induced cost function is convex. We leverage this insight to develop a combinatorial algorithm that solves the corresponding problem in O(n log n) 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