In the bottleneck hyperplane clustering problem, given n points in ℝd and an integer k with 1≤k≤n, we wish to determine k hyperplanes and assign each point to a hyperplane so as to minimize the maximum Euclidean distance between each point and its assigned hyperplane. This mixed-integer nonlinear problem has several interesting applications but is computationally challenging due, among others, to the nonconvexity arising from the ℓ2-norm. After comparing several linear approximations to deal with the ℓ2-norm constraint, we propose a two-phase heuristic. First, an approximate solution is obtained by exploiting the ℓ∞-approximation and the problem geometry, and then it is converted into an ℓ2-approximate solution. Computational experiments on realistic randomly generated instances and instances arising from piecewise affine maps show that our heuristic provides good quality solutions in a reasonable amount of time.

A two-phase heuristic for the bottleneck k-hyperplane clustering problem

AMALDI, EDOARDO;DHYANI, KANIKA;
2013-01-01

Abstract

In the bottleneck hyperplane clustering problem, given n points in ℝd and an integer k with 1≤k≤n, we wish to determine k hyperplanes and assign each point to a hyperplane so as to minimize the maximum Euclidean distance between each point and its assigned hyperplane. This mixed-integer nonlinear problem has several interesting applications but is computationally challenging due, among others, to the nonconvexity arising from the ℓ2-norm. After comparing several linear approximations to deal with the ℓ2-norm constraint, we propose a two-phase heuristic. First, an approximate solution is obtained by exploiting the ℓ∞-approximation and the problem geometry, and then it is converted into an ℓ2-approximate solution. Computational experiments on realistic randomly generated instances and instances arising from piecewise affine maps show that our heuristic provides good quality solutions in a reasonable amount of time.
2013
Approximations; Heuristics; Hyperplane clustering; Hyperplane cover problem; k-Hyperplane center problem; Mixed integer nonlinear formulation
File in questo prodotto:
File Dimensione Formato  
COAP-13.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 561.61 kB
Formato Adobe PDF
561.61 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/770496
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact