التفاصيل البيبلوغرافية
| العنوان: |
Inverse median location problems with variable coordinates. |
| المؤلفون: |
Baroughi Bonab, Fahimeh, Burkard, Rainer, Alizadeh, Behrooz |
| المصدر: |
Central European Journal of Operations Research; Sep2010, Vol. 18 Issue 3, p365-381, 17p |
| مصطلحات موضوعية: |
COORDINATES, LOCATION problems (Programming), COMBINATORIAL optimization, MEDIAN (Mathematics), MATHEMATICAL analysis, APPROXIMATION theory, ALGORITHMS, CHEBYSHEV polynomials |
| مستخلص: |
Given n points in $${\mathbb{R}^d}$$ with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in $${\mathbb{R}^d}$$ becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is $${\mathcal{NP}}$$-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O( nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O( nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is $${\mathcal{NP}}$$-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist. [ABSTRACT FROM AUTHOR] |
|
Copyright of Central European Journal of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
Full Text Finder