On some inverse 1-center location problems

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 ${\mathbb{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 ${\mathbb{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.

KEYWORDS:

• Location problem
• inverse optimization
• 1-center
• interval graph

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 90B10
• 90B80
• 90C27

Acknowledgements

The authors would like acknowledge the anonymous referees for valuable suggestions which help to improve this paper significantly.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Kien Trung Nguyen http://orcid.org/0000-0002-7522-4557

Additional information

Funding

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