Inverse stable point problem on trees under an extension of Chebyshev norm and Bottleneck Hamming distance. (4th July 2021)

• Record Type: Journal Article
• Authors: Pham, Van Huy; Nguyen, Kien Trung; Le, Tran Thu
• Is Part Of: Optimization methods and software. Volume 36:Number 4(2021)
• Page Start: 755
• Page End: 772
• Publication Date: 2021-07-04
• Subjects: Location problem -- inverse optimization -- Chebyshev norm -- Hamming distance -- tree; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1713778
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: In the inverse optimization problem, we modify parameters of the original problem at minimum total cost so as to make a prespecified solution optimal with respect to new parameters. We extend in this paper a class of inverse single facility problems on trees, including inverse balance point, inverse 1-median and inverse 1-center problem, and call it the inverse stable point problem. For the general situation where variables are both edge lengths and vertex weights under an extension of Chebyshev norm and bottleneck Hamming distance, we first derive an algorithm that reduces the corresponding problem to the one under either Chebyshev norm or bottleneck Hamming distance and then develop an approximation approach for the problem. Special cases concerning the problem under this extension with strongly polynomial time algorithms are also discussed.