๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A localization property for facility-location problems with arbitrary norms

โœ Scribed by Henrik Juel; Robert Love

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
189 KB
Volume
35
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

โœฆ Synopsis

In an earlier article we showed that, for facilities-location problems characterized by generalized distance norms and any even number of existing facilities, the optimal location of the new facility is at the intersection of the lines joining the pairs of facilities if these lines intersect at a single point. In this article we extend this concept to show that, for a more general class of problems, the optimal location is one of a set of points which is specified by the existing facilities.

๐Ÿ“œ SIMILAR VOLUMES

Analysis of a Local Search Heuristic for
Analysis of a Local Search Heuristic for Facility Location Problems
โœ Madhukar R. Korupolu; C.Greg Plaxton; Rajmohan Rajaraman ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 258 KB

In this paper, we study approximation algorithms for several NP-hard facility location problems.We prove that a simple local search heuristic yields polynomialtime constant-factor approximation bounds for the metric versions of the uncapacitated k-median problem and the uncapacitated facility locati