tailieunhanh - Sum-of-Squares clustering on networks

Finding p prototypes by minimizing the sum of the squared distances from a set of points to its closest prototype is a well-studied problem in clustering, data analysis and continuous location. In this note, this very same problem is addressed assuming, for the first time, that the space of possible prototype locations is a network. We develop some interesting properties of such clustering problem. We also show that optimal cluster prototypes are not necessary located at vertices of the network. | Yugoslav Journal of Operations Research 21 (2011), Number 2, 157-161 DOI: SUM-OF-SQUARES CLUSTERING ON NETWORKS Emilio CARRIZOSA Faculdad de Matemáticas, Universidad de Sevilla, Spain, ecarrizosa@ Nenad MLADENOVIĆ School of Mathematics, Brunel University-West London, UK, Raca TODOSIJEVIĆ Faculty of Mathematics, University of Belgrade, Serbia, racatodosijevic@ Received: October 2011 / Accepted: December 2011 Abstract: Finding p prototypes by minimizing the sum of the squared distances from a set of points to its closest prototype is a well-studied problem in clustering, data analysis and continuous location. In this note, this very same problem is addressed assuming, for the first time, that the space of possible prototype locations is a network. We develop some interesting properties of such clustering problem. We also show that optimal cluster prototypes are not necessary located at vertices of the network. Keywords: Networks, clustering, location, p-Median. MSC: 90C35, 90C30. 1. INTRODUCTION Let N (V , E ) be a connected and undirected network with a node set V and an edge set E . Each edge is represented by its endpoints and its length. Let x be a point on an edge, then its location is determined by its distance from a prescribed endpoint of that edge. If an edge has endpoints (u, v) and length l, then any real number x ∈ [0,l] denotes the location in that edge for which the length of sub-edge [u, x] is x . For any two points x and y in N , let d ( x, y ) denote the length of a shortest path connecting x and y. For 158 E. Carrizosa, N. Mladenović, R. Todosijević / Sum-Of-Squares Clustering any nonempty finite set P of points, let d ( x, P ) denote the minimum distance from x to P , d ( x, P ) = min {d ( x, p) : p ∈ P} (1) Consider a set P of p locations for prototypes on a network N and suppose that the cardinality of the set V is equal to n. Let each vertex x i ∈ V has .