Worst-Case and Probabilistic Analysis of a Geometric Location Problem
Lists
Only you see this
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...