Actas de congresos
A Continuous Facility Location Problem And Its Application To A Clustering Problem
Registro en:
9781595937537
Proceedings Of The Acm Symposium On Applied Computing. , v. , n. , p. 1826 - 1831, 2008.
10.1145/1363686.1364126
2-s2.0-56749181211
Autor
Meira L.A.A.
Miyazawa F.K.
Institución
Resumen
We consider a new problem, which we denote by Continuous Facility Location (ConFL), and its application to the k-Means Problem. Problem ConFL is a natural extension of the Uncapacitated Facility Location Problem where a facility can be any point in ℝq. The proposed algorithms are based on a primal-dual technique for spaces with constant dimensions. For the ConFL Problem, we present algorithms with approximation factors 3+ε and 1.861+ε for euclidean distances and 9+ε for squared euclidean distances. For the k-Means Problem (that is restricted to squared euclidean distance), we present an algorithm with approximation factor 54 +ε. All algorithms have good practical behaviour in small dimensions. Comparisons with known algorithms show that the proposed algorithms have good practical behaviour. Copyright 2008 ACM.
1826 1831 Arora, S., Raghavan, P., Rao, S., Approximation schemes for euclidean k-medians and related problems (1998) Proc. of the 30th ACM Symposium on Theory of computing, pp. 106-113 Drineas, P., Frieze, A., Kannan, R., Vempala, S., Vinay, V., Clustering large graphs via the singular value decomposition (2004) Mach. Learning, 56, pp. 9-33 Du, Q., Faber, V., Gunzburger, M., Centroidal voronoi tessellations: Applications and algorithms (1999) SIAM Review, 41 (4), pp. 637-676 Guha, S., Khuller, S., Greedy strikes back: Improved facility location algorithms (1999) Journal of Algorithms, 31, pp. 228-248 Hochbaum, D.S., Heuristics for the fixed cost median problem (1982) Math. Programming, 22 (2), pp. 148-162 Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V., Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP (2003) Journal of the ACM, 50 (6), pp. 795-824 Jain, K., Mahdian, M., Saberi, A., A new greedy approach for facility location problems (2002) Proc. of the 34th ACM Symposium on Theory of Computing, pp. 731-740 Jain, K., Vazirani, V.V., Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation (2001) Journal of the ACM, 48 (2), pp. 274-296 Kanungo, T., Mount, D., Netanyahu, N., Piatko, C., Silverman, R., Wu, A., An efficient k-means clustering algorithm: Analysis and implementation (2002) IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, pp. 881-892 Kanungo, T., Mount, D., Netanyahu, N., Piatko, C., Silverman, R., Wu, A., A local search approximation algorithm for k-means clustering (2004) Computational Geometry: Theory and Applications, 28, pp. 89-112 Kumar, A., Sabharwal, Y., Sen, S., A simple linear time (1+ε)-approximation algorithm for k-means clustering in any dimensions (2004) Proc. 45th IEEE Symp. on Found. of Comp. Sci, pp. 454-462 Li, Y., A newton acceleration of the weiszfeld algorithm forminimizing the sum of euclidean distances (1998) Comput. Opt. and Appl, 10 (3), pp. 219-242 Lloyd, S.P., Least squares quantization in pcm (1982) IEEE Trans. on Information Theory, 28 (2), pp. 129-137 Mahdian, M., Ye, Y., Zhang, J., Approximation algorithms for metric facility location problems (2006) SIAM Journal on Computing, 36 (2), pp. 411-432 Matousek, J., On approximate geometric k-clustering (2000) Discrete Computational Geometry, 24 (1), pp. 61-84 Shmoys, D., Tardos, E., Aardal, K., Approximation algorithms for facility location problems (1997) Proc. of the 29th ACM Symposium on Theory of Computin, pp. 265-274 Weiszfeld, E., Sur le point pour lequel la somme des distances de n points donnes est minimum (1937) Tohoku Math. Journal, 43, pp. 355-386 Xue, G., Ye, Y., An efficient algorithm for minimizing a sum of p-norms (1999) SIAM J. on Optimization, 10 (2), pp. 551-579