Global Convergence of a Generalized Iterative Procedure for the Minisum Location Problem with lp Distances

Abstract

This paper considers a general form of the single facility minisum location problem (also referred to as the Fermat-Weber problem), where distances are measured by an lp norm. An iterative solution algorithm is given which generalizes the well-known Weiszfeld procedure for Euclidean distances. Global convergence of the algorithm is proven for any value of the parameter p in the closed interval [1, 2], provided an iterate does not coincide with a singular point of the iteration functions. However, for p > 2, the descent property of the algorithm and as a result, global convergence, are no longer guaranteed. These results generalize the work of Kuhn for Euclidean (p = 2) distances.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 86 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.