Authors: Carrizosa, Emilio
Mladenović, Nenad 
Todosijević, Raca 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable neighborhood search for minimum sum-of-squares clustering on networks
Journal: European Journal of Operational Research
Volume: 230
Issue: 2
First page: 356
Last page: 363
Issue Date: 16-Oct-2013
Rank: M21a
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2013.04.027
Euclidean Minimum Sum-of-Squares Clustering amounts to finding p prototypes by minimizing the sum of the squared Euclidean distances from a set of points to their closest prototype. In recent years related clustering problems have been extensively analyzed under the assumption that the space is a network, and not any more the Euclidean space. This allows one to properly address community detection problems, of significant relevance in diverse phenomena in biological, technological and social systems. However, the problem of minimizing the sum of squared distances on networks have not yet been addressed. Two versions of the problem are possible: either the p prototypes are sought among the set of nodes of the network, or also points along edges are taken into account as possible prototypes. While the first problem is transformed into a classical discrete p-median problem, the latter is new in the literature, and solved in this paper with the Variable Neighborhood Search heuristic. The solutions of the two problems are compared in a series of test examples.
Keywords: Minimum sum-of-squares clustering Location on networks Variable neighborhood search
Publisher: Elsevier
Project: Serbian–Spanish project AIB2010SE-00318
MTM2009-14039, MTM2012-36163 (Ministry of Science and Innovation, Spain)
FQM-329 (Junta de Andalucia, Spain)
Serbian Ministry of Sciences, Grant no. 172010

Show full item record


checked on May 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.