Worst-case and Probabilistic Analysis of a Geometric Location Problem
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 solu...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148980 |