Find in Library

With many efficient solutions for a multi-objective optimization problem, this paper aims to cluster the Pareto Front in a given number of clusters <i>K</i> and to detect isolated points. <i>K</i>-center problems and variants are investigated with a unified formulation considering the discrete and continuous versions, partial <i>K</i>-center problems, and their min-sum-<i>K</i>-radii variants. In dimension three (or upper), this induces NP-hard complexities. In the planar case, common optimality property is proven: non-nested optimal solutions exist. This induces a common dynamic programming algorithm running in polynomial time. Specific improvements hold for some variants, such as <i>K</i>-center problems and min-sum <i>K</i>-radii on a line. When applied to N points and allowing to uncover <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>M</mi><mo><</mo><mi>N</mi></mrow></semantics></math></inline-formula> points, K-center and min-sum-<i>K</i>-radii variants are, respectively, solvable in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>K</mi><mo>(</mo><mi>M</mi><mo>+</mo><mn>1</mn><mo>)</mo><mi>N</mi><mo form="prefix">log</mo><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>K</mi><mrow><mo>(</mo><mi>M</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><msup><mi>N</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> time. Such complexity of results allows an efficient straightforward implementation. Parallel implementations can also be designed for a practical speed-up. Their application inside multi-objective heuristics is discussed to archive partial Pareto fronts, with a special interest in partial clustering variants.