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

Edoardo Amaldi (), Kanika Dhyani () and Leo Liberti ()

Computational Optimization and Applications, 2013, vol. 56, issue 3, 619-633

Abstract: In the bottleneck hyperplane clustering problem, given n points in $\mathbb{R}^{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. Copyright Springer Science+Business Media New York 2013

Keywords: Hyperplane clustering; Hyperplane cover problem; k-Hyperplane center problem; Mixed integer nonlinear formulation; Approximations; Heuristics (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9567-2 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:56:y:2013:i:3:p:619-633

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9567-2

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().