Worst-Case and Probabilistic Analysis of a Geometric Location Problem

Christos H. Papadimitriou

Abstract

We consider the problem of choosing K “medians” among n points on the Euclidean plane such that the sum of the distances from each of the n points to its closest median is minimized. We show that this problem is NP-complete. We also present two heuristics that produce arbitrarily good solutions with probability going to 1. One is a partition heuristic, and works when K grows linearly—or almost so—with n. The other is the “honeycomb” heuristic, and is applicable to rates of growth of K of the form $K \sim n^\varepsilon $, $0 < \varepsilon < 1$.
BibTeX
@article{papadimitriou1981worst,
  author = {Christos H. Papadimitriou},
  title = {{Worst-Case and Probabilistic Analysis of a Geometric Location Problem}},
  journal = {SIAM Journal on Computing},
  year = {1981},
  url = {https://openreview.net/forum?id=bIw5JkyTU23},
}

Loading related content...

Figure