We consider in this paper the inverse versions of the two popular problems in location theory, say the 1-median and the 1-center problems on trees. The cost for modifying vertex weights is measured under l_k-norm for a positive integer k and hence the cost function is nonlinear. For the inverse 1-median problem, we develop a linear time algorithm based on the optimal solution of the induced unconstrained problem. For the inverse 1-center problem, we prove that the problem can be decomposed into linearly many subproblems and the objective function in each subproblem is piecewise-convex. Furthermore, we also discuss an O(nlog n) time algorithm for the inverse 1-center problem under l_2-norm based on the convexity of the cost function of each subproblem.
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