Revisiting several problems and algorithms in continuous location with ${\ell }_p$ norms

Abstract

This paper addresses the general continuous single facility location problems in finite dimension spaces under possibly different ${\ell }_p$ norms in the demand points. We analyze the difficulty of this family of problems and revisit convergence properties of some well-known algorithms. The ultimate goal is to provide a common approach to solve the family of continuous ${\ell }_p$ ordered median location problems in dimension $d$ (including of course the ${\ell }_p$ minisum or Fermat-Weber location problem for any $p\ge 1$). We prove that this approach has a polynomial worse case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems.

31 pages, 5 tables

References in corpus (1)

• Semidefinite Representation of Convex Sets

Cited by in corpus (1)

• Optimal arrangements of hyperplanes for multiclass classification