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

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 ℓ₂-norm. After comparing several linear approximations to deal with the ℓ₂-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 ℓ₂-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.