1835. An incremental exact algorithm for the hyper-rectangular clustering problem with axis-parallel clusters
Invited abstract in session TC-20: Exact algorithms for combinatorial optimization, stream Combinatorial Optimization.
Tuesday, 12:30-14:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Diego Delle Donne
|
| IDS department, ESSEC Bussines School | |
| 2. | Javier Marenco
|
| Business School, Universidad Torcuato Di Tella | |
| 3. | Eduardo Moreno
|
| Google Research |
Abstract
Given a set of points in the d-dimensional space, a hyper-rectangle clustering is a partition of the set of points into groups called clusters, where each cluster is determined by the smallest hyper-rectangle containing the points in the cluster. We address the problem of finding a hyper- rectangle clustering of minimum size. Previous exact approaches to this problem are mostly based on integer programming formulations and can only solve to optimality instances of small size. In this work we propose an adaptive exact strategy which takes advantage of the capacity to solve small instances to optimality of previous approaches. Our algorithm starts by solving an instance with a small subset of points and iteratively adds more points if these are not covered by the obtained solution. We prove that as soon as a solution covers the whole set of point from the instance, then the solution is actually an optimal solution for the original problem. We compare the efficiency of the new method against the existing ones with an exhaustive computational experimentation in which we show that the new approach is able to solve to optimality instances of higher orders of magnitude.
Keywords
- Algorithms
- Combinatorial Optimization
- Machine Learning
Status: accepted
Back to the list of papers