Sum-of-squares clustering on networks
DOI:
https://doi.org/10.2298/YJOR1102157CKeywords:
networks, clustering, location, p-MedianAbstract
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.References
Francis, R.L., Lowe, T.J., Rayco, M.B., and Tamir, A., "Aggregation error for location models: survey and analysis", Annals of Operations Research, Springer, (2009) 171-208.
Hansen, P., and Labbe', M., "The continuous p-Median of a network", Networks, 19 (1989) 595-606.
Hassin, R., and Tamir, A., "Improved complexity bounds for location problems on the real line", Operations Research Letters, 10 (1991) 395-402.
Lopez-de-los-Mozos, M., and Mesa, J., "The maximum absolute deviation measure in location problems on networks", European Journal of Operational Research, 135 (2001) 184-194.
Lopez-de-los-Mozos, M., Mesa, J., and Puerto, J., "A generalized model of equality measures in network location problems", Computers and Operations Research, 35 (2008) 651-660.
Mladenović, N., and Hansen, P., "Variable neighborhood search", Computers and Operations Research, 24 (1997) 1097-1100.
Perez-Brito, D., Mladenović, N., and Moreno-Perez, J.A., "A note on spanning trees for network location problems", Yugoslav Journal of Operations Research, 8 (1) (1998).
Downloads
Published
Issue
Section
License
Copyright (c) 2011 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
