Computing sharp bounds for hard clustering problems on trees |
| |
Authors: | Isabella Lari Maurizio Maravalle |
| |
Institution: | a Department of Statistics, “La Sapienza” University, Piazzale A. Moro 5, 00185 Rome, Italy b Department of Systems and Institutions for Economics, University of L’Aquila, Piazza del Santuario 19, 67040 Roio Poggio, L’Aquila, Italy |
| |
Abstract: | Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution networks, districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose heuristics that find good partitions within a reasonable time, even for instances of relatively large size. Such heuristics are based on the solution of continuous relaxations of certain integer (or almost integer) linear programs. Experimental results on over 2000 randomly generated instances with up to 500 entities show that the values (total within-cluster dissimilarity or diameter) of the solutions provided by these heuristics are quite close to the minimum one. |
| |
Keywords: | Contiguity-constrained clustering Trees Heuristics Computational complexity Linear programming Integer programming |
本文献已被 ScienceDirect 等数据库收录! |
|