This paper concerns the problem of reducing the edge lengths of a tree in a minimum cost way such that the 1-center function at a predetermined vertex is at most a given threshold value. Moreover, it is assumed that the costs of reducing edge lengths are not exactly determined, but they are estimated within intervals and their total deviation is limited within a given bound. This problem is called the robust reverse 1-center problem on trees with interval costs. We first reformulate the problem as a Stackelberg game and translate it into a univariate optimization problem. Based on the special properties of the feasible set, we can state the corresponding problem as a parameterized minimum cost flow problem. Then we develop an algorithm that solves the problem in O(n^2 log n) time due to the convexity of the univariate objective function. We finally discuss the problem of improving the international transportation network in Iran as a real-life application.
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