Abstract
In this note we first show that the centroid (or centre of gravity) gives in value a (σ+1)-approximation to any continuous single facility minisum location problem
for any gauge with asymmetry measure σ,
and thus a 2-approximate solution for any norm.
On the other hand for any gauge the true minimum point (the 1-median)
remains within a bounded set whenever a fixed proportion of
less than half of the total weight of the destination points
is moved to any other positions. It follows that the distance between the centroid and the 1-median
may be arbitrary close to half the diameter of the destination set.
Original language | English |
---|---|
Pages (from-to) | 98-102 |
Number of pages | 5 |
Journal | European Journal of Operational Research |
Volume | 252 |
Issue number | 1 |
Early online date | 11 Jan 2016 |
DOIs | |
Publication status | Published - 1 Jul 2016 |
Keywords
- Fermat-Weber problem
- 1-median
- 2-approximation
- gauge
- breakdown point