On some inverse 1-center location problems. (4th May 2019)

• Record Type: Journal Article
• Authors: Nguyen, Kien Trung; Hung, Nguyen Thanh; Nguyen-Thu, Huong; Le, Tran Thu; Pham, Van Huy
• Is Part Of: Optimization. Volume 68:Number 5(2019)
• Page Start: 999
• Page End: 1015
• Publication Date: 2019-05-04
• Subjects: Location problem -- inverse optimization -- 1-center -- interval graph; 90B10 -- 90B80 -- 90C27; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2019.1571056
• Languages: English
• ISSNs: 0233-1934

Abstract

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.