Let a ground set E and a prespecified element be given. We address the problem of modifying the weight of each element in E at minimum cost so that the weight of the prespecified element become the maximum one in the perturbed set. Moreover, as modifying costs are usually uncertain in many real life situations, we measure the robustness by taking into account the minmax regret inverse maximum weight problem on E. In order to solve the problem, we first prove that there are exactly two scenarios that lead to the maximum regret of the cost function. Based on the convexity of the objective function, we develop a combinatorial algorithm that solves the corresponding problem in linear 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