Inverse median location problems with variable coordinates
Fahimeh Baroughi Bonab (baroughi@opt.math.tugraz.at),
Rainer Burkard (burkard@opt.math.tugraz.at) and
Behrooz Alizadeh (alizadeh@opt.math.tugraz.at)
Central European Journal of Operations Research, 2010, vol. 18, issue 3, 365-381
Abstract:
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. Copyright Springer-Verlag 2010
Keywords: Location problem; 1-median; Inverse optimization; Combinatorial optimization (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (9)
Downloads: (external link)
http://hdl.handle.net/10.1007/s10100-009-0114-2 (text/html)
Access to full text is restricted to subscribers.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:18:y:2010:i:3:p:365-381
Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100
DOI: 10.1007/s10100-009-0114-2
Access Statistics for this article
Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger
More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).