direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2000

On the continuous Weber and k-median problems
Zitatschlüssel Report-666-2000
Autor Sándor P. Fekete and Joseph S. B. Mitchell and Karin Weinbrecht
Jahr 2000
Nummer 666
Notiz Extended abstract in: 16th Annual Symposium on Computational Geometry (SoCG 2000), 70–79
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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 $L_1$ 1-median (Weber) problem. We also consider the multiple-center version of the $L_1$ $k$-median problem, which we prove is NP-hard for large $k$.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag