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

In the bottleneck hyperplane clustering problem, given n points in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb{R}^{d}$</EquationSource> </InlineEquation> 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 ℓ <Subscript>2</Subscript>-norm. After comparing several linear approximations to deal with the ℓ <Subscript>2</Subscript>-norm constraint, we propose a two-phase heuristic. First, an approximate solution is obtained by exploiting the ℓ <Subscript>∞</Subscript>-approximation and the problem geometry, and then it is converted into an ℓ <Subscript>2</Subscript>-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. Copyright Springer Science+Business Media New York 2013