How bad can the centroid be?

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)98-102
Number of pages5
JournalEuropean Journal of Operational Research
Volume252
Issue number1
Early online date11 Jan 2016
DOIs
Publication statusPublished - 1 Jul 2016

Keywords

  • Fermat-Weber problem
  • 1-median
  • 2-approximation
  • gauge
  • breakdown point

Fingerprint

Dive into the research topics of 'How bad can the centroid be?'. Together they form a unique fingerprint.

Cite this