We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks.
- Authors
Nguyen, Kien Trung; Nguyen-Thu, Huong; Hung, Nguyen Thanh
- Abstract
An ordered median function is used in location theory to generalize a class of problems, including median and center problems. In this paper we consider the complexity of inverse ordered 1-median problems on the plane and on trees, where the multipliers are sorted nondecreasingly. Based on the convexity of the objective function, we prove that the problems with variable weights or variable coordinates on the line are NP-hard. Then we can directly get the NP-hardness result for the corresponding problem on the plane. We finally develop a cubic time algorithm that solves the inverse convex ordered 1-median problem on trees with relaxation on modification bounds.
- Subjects
LOCATION theory (Geography); PLANES (Hand tools); TREES; MULTIPLIERS (Mathematical analysis); ECONOMIC geography
- Publication
Mathematical Methods of Operations Research, 2018, Vol 88, Issue 2, p147
- ISSN
1432-2994
- Publication type
Article
- DOI
10.1007/s00186-018-0632-6