Inverse stable point problem on trees under an extension of Chebyshev norm and Bottleneck Hamming distance

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.

Keywords:

• Location problem
• inverse optimization
• Chebyshev norm
• Hamming distance
• tree

Acknowledgments

The authors thank the anonymous referees for their valuable comments which improved the quality of the paper significantly.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 101.01-2019.325.

Notes on contributors

Van Huy Pham

Van Huy Pham received the PhD degree in computer science from Ulsan University (South Korea) in 2015. From 2004 to 2010, he was a lecturer at Can Tho University (Vietnam). Since 2015, he has been a lecturer and researcher at Faculty of Information Technology, Ton Duc Thang University (Vietnam). His main research interest includes artificial intelligence, image processing, computer vision, and algorithm.

Kien Trung Nguyen

Kien Trung Nguyen received his PhD at Kaiserslautern University of Technology (Germany) in the specialization of combinatorial optimization. His research interests include location theory, inverse combinatorial optimization, and operations research. Dr Nguyen is currently a lecturer at Can Tho University (Vietnam).

Tran Thu Le

Tran Thu Le received BSc degree at Can Tho University (Vietnam) in the field of Mathematics Education. His research topic is inverse location theory. He currently attends the master course in Mathematics at University of Rennes 1 (France), that was financially supported by Lebesgue scholarship.