Portal de Periódicos da CAPES

Worst-Case and Probabilistic Analysis of a Geometric Location Problem

1981; Society for Industrial and Applied Mathematics; Volume: 10; Issue: 3 Linguagem: Inglês

10.1137/0210040

1095-7111

Christos H. Papadimitriou,

Vehicle Routing Optimization Methods

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$.