×

zbMATH — the first resource for mathematics

A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems. (English) Zbl 1271.90094
Comput. Optim. Appl. 54, No. 3, 675-703 (2013); erratum ibid. 54, No. 3, 705-705 (2013).
Summary: The \(k\)-center problem arises in many applications such as facility location and data clustering. Typically, it is solved using a branch and bound tree traversed using the depth first strategy. The reason is its linear space requirement compared to the exponential space requirement of the breadth first strategy. Although the depth first strategy gains useful information fast by reaching some leaves early and therefore assists in pruning the tree, it may lead to exploring too many subtrees before reaching the optimal solution, resulting in a large search cost. To speed up the arrival to the optimal solution, a mixed breadth-depth traversing strategy is proposed. The main idea is to cycle through the nodes of the same level and recursively explore along their first promising paths until reaching their leaf nodes (solutions). Thus many solutions with diverse structures are obtained and a good upper bound of the optimal solution can be achieved by selecting the minimum among them. In addition, we employ inexpensive lower and upper bounds of the enclosing balls, and this often relieves us from calling the computationally expensive exact minimum enclosing ball algorithm. Experimental work shows that the proposed strategy is significantly faster than the naked branch and bound approach, especially as the number of centers and/or the required accuracy increases.

MSC:
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Acharya, T., Ray, A.K.: Image Processing: Principles and Applications. Wiley, New York (2005)
[2] Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. In: Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 658–667 (1998) · Zbl 0930.68168
[3] Bǎdoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. 34th Annual ACM Symposium on Theory of computing (STOC’2002), pp. 250–257 (2002) · Zbl 1192.68871
[4] Bǎdoiu, M., Clarkson, K.L.: Smaller core-sets for balls. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 801–802 (2003) · Zbl 1092.68660
[5] Bilò, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Geometric clustering to minimize the sum of cluster sizes. In: Proc. of the European Symposium on Algorithms. LNCS, vol. 3669, pp. 460–471 (2005) · Zbl 1162.68735
[6] Blake, C.L., Merz, C.J.: UCI repository of machine learning databases. Dept. Inf. Comput. Sci., Univ. California, Tech. Rep. (1998). http://archive.ics.uci.edu/ml/datasets
[7] Brandenberg, R., Roth, L.: New algorithms for k-center and extensions. J. Comb. Optim. 18, 376–392 (2009) · Zbl 1184.90133 · doi:10.1007/s10878-009-9226-9
[8] Cook, W.J.: National traveling salesman problems. http://www.tsp.gatech.edu/world/countries.html · Zbl 1019.90520
[9] Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification, 2nd edn. Wiley, New York (2001)
[10] Farahani, R.Z., Hekmatfar, M.: Facility Location: Concepts, Models, Algorithms and Case Studies. Physica-Verlag, Heidelberg (2009)
[11] Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12, 133–137 (1981) · Zbl 0469.68053 · doi:10.1016/0020-0190(81)90111-3
[12] Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293–306 (1985) · Zbl 0567.62048 · doi:10.1016/0304-3975(85)90224-5
[13] Hastie, T., Tibshirani, R., Friedman, J.H.: The Elements of Statistical Learning: Data Mining Inference, and Prediction. Springer, Berlin (2001) · Zbl 0973.62007
[14] Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice Hall, New York (1988) · Zbl 0665.62061
[15] Jain, A.K., Murthy, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Rev. 31(3), 264–323 (1999)
[16] Kowalski, G.: Information Retrieval Architecture and Algorithms. Springer, Berlin (2010) · Zbl 1216.68100
[17] Kumar, P., Mitchell, J.S.B., Yildirim, A.: Computing core-sets and approximate smallest enclosing HyperSpheres in high dimensions. In: Proc. 5th Workshop on Algorithm Engineering and Experiments, pp. 45–55. SIAM, Philadelphia (2003)
[18] Kumar, P., Mitchell, J.S.B., Yildirim, A.: Approximate minimum enclosing balls in high dimensions using core-sets. ACM J. Exp. Algorithmics 8, 1–29 (2003) · Zbl 1083.68138
[19] Kumar, P.: Clustering and reconstructing large data sets. PhD thesis, Department of Computer Science, Stony Brook University (2004)
[20] Kumar, P., Kumar, P.: Almost optimal solutions to k-clustering problems. Int. J. Comput. Geom. Appl. 20(4), 431–447 (2010) · Zbl 1198.65044 · doi:10.1142/S0218195910003372
[21] Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. 47, 489–501 (2005) · Zbl 1079.68505 · doi:10.1016/j.comnet.2004.08.012
[22] Megiddo, N.: Linear-time algorithms for linear programming in R 3 and related problems. SIAM J. Comput. 13, 759–776 (1983) · Zbl 0521.68034 · doi:10.1137/0212052
[23] Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM J. Comput. 13, 182–196 (1984) · Zbl 0534.68032 · doi:10.1137/0213014
[24] Mehrotra, S.: On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4), 575–601 (1992) · Zbl 0773.90047 · doi:10.1137/0802028
[25] Reinelt, G.: TSPLIB, a traveling salesman problem library. ORSA J. Comput. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95 · Zbl 0775.90293
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.