direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 666-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

On the continuous Weber and k-median problems
Sándor P. Fekete, Joseph S. B. Mitchell, and Karin Weinbrecht
Extended abstract in: 16th Annual Symposium on Computational Geometry (SoCG 2000), 70-79
primary: 90B85 Continuous location
secondary: 68U05 Computer graphics; computational geometry
location theory, Weber problem, k-median, median, continuous demand, computational geometry, geometric optimization, shortest paths, rectilinear norm, computational complexity
We give the first exact algorithmic study of facility location problems having a continuum of demand points. In particular, we consider versions of the "continuous k-median (Weber) problem" where the goal is to select one or more center points that minimize average distance to a set of points in a demand region. In such problems, the average is computed as an integral over the relevant region, versus the usual discrete sum of distances. The resulting facility location problems are inherently geometric, requiring analysis techniques of computational geometry. We provide polynomial-time algorithms for various versions of the L1 1-median (Weber) problem. We also consider the multiple-center version of the L1 k-median problem, which we prove is NP-hard for large k.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe