Revisiting several problems and algorithms in continuous location with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\ell _\tau $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>ℓ</mi> <mi mathvariant="italic">τ</mi> </msub> </math> </EquationSource> </InlineEquation> norms
This paper addresses the general continuous single facility location problems in finite dimension spaces under possibly different <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$\ell _\tau $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>ℓ</mi> <mi mathvariant="italic">τ</mi> </msub> </math> </EquationSource> </InlineEquation> norms, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$\tau \ge 1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="italic">τ</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$\ell _\tau $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>ℓ</mi> <mi mathvariant="italic">τ</mi> </msub> </math> </EquationSource> </InlineEquation> ordered median location problems Nickel and Puerto (Facility location: a unified approach, <CitationRef CitationID="CR42">2005</CitationRef>) in dimension <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$$d$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>d</mi> </math> </EquationSource> </InlineEquation> (including of course the <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$$\ell _\tau $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi>ℓ</mi> <mi mathvariant="italic">τ</mi> </msub> </math> </EquationSource> </InlineEquation> minisum or Fermat-Weber location problem for any <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$$\tau \ge 1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="italic">τ</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>). We prove that this approach has a polynomial worst case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems. Copyright Springer Science+Business Media New York 2014
