Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14666
For citation please use:
Main Title: On the continuous Weber and k-median problems
Author(s): Fekete, Sándor P.
Mitchell, Joseph S. B.
Weinbrecht, Karin
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15893
http://dx.doi.org/10.14279/depositonce-14666
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: 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.
Subject(s): location theory
Weber problem
k-median
median
continuous demand
computational geometry
geometric optimization
shortest paths
rectilinear norm
computational complexity
Issue Date: 2000
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90B85 Continuous location
68U05 Computer graphics; computational geometry
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2000, 666
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-666-2000.pdf
Format: Adobe PDF | Size: 16.17 MB
DownloadShow Preview
Thumbnail
Report-666-2000.ps.gz
Format: Unknown | Size: 157.82 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.