In location theory, the 1-centdian function is a convex combination of the 1-median and the 1-center functions. We consider the uniform cost reverse 1-centdian problem on networks, where edge lengths are reduced within a given budget such that the 1-centdian function at a prespecified point on the network is minimized. We first prove that the problem on general networks is NP-hard by reducing the set cover problem to it. Then, we focus on the special case of the problem on tree networks. Based on the strategy that we reduce either one edge or several edges simultaneously in each step to obtain an optimal solution, we develop a combinatorial algorithm that solves the corresponding problem on trees in quadratic 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