On some inverse 1-center location problems. (4th May 2019) - Nguyen, Kien Trung; Hung, Nguyen Thanh; Nguyen-Thu, Huong; Le, Tran Thu; Pham, Van Huy
ABSTRACT: This paper addresses two problems, the inverse 1-center problem on the line with closed-interval facilities and the inverse 1-center problem on R d . For the first problem, we develop a combinatorial O ( n log ⁡ n ) algorithm based on the convexity of the objective function, where n is the number of facilities. We also discuss the corresponding problem on interval graphs with the similar solution approach. Concerning the inverse 1-center problem on R d, we propose an O ( d n 2 log ⁡ n ) algorithm based on the optimality criterion, where n is the number of existing points.