{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:14Z","timestamp":1774421294637,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540850960","type":"print"},{"value":"9783540850977","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_7","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T07:18:26Z","timestamp":1219130306000},"page":"64-78","source":"Crossref","is-referenced-by-count":3,"title":["New Algorithms for k-Center and Extensions"],"prefix":"10.1007","author":[{"given":"Ren\u00e9","family":"Brandenberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucia","family":"Roth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. In: Proc. 9th ACM-SIAM Symp. Discrete Alg., pp. 658\u2013667 (1998)"},{"issue":"4","key":"7_CR2","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Comput. Surv.\u00a030(4), 412\u2013458 (1998)","journal-title":"ACM Comput. Surv."},{"key":"7_CR3","series-title":"Probability and mathematical statistics","volume-title":"Cluster analysis for applications","author":"M.R. Anderberg","year":"1973","unstructured":"Anderberg, M.R.: Cluster analysis for applications. Probability and mathematical statistics. Academic Press, London (1973)"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02187699","volume":"1","author":"D. Avis","year":"1986","unstructured":"Avis, D.: Diameter partitioning. Discrete Comput. Geom.\u00a01, 265\u2013276 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"7_CR5","unstructured":"Bespamyatnikh, S., Kirkpatrick, D.: Rectilinear 2-center problems. In: Proc.\u00a011th Canad.\u00a0Conf.\u00a0Comp.\u00a0Geom., pp. 68\u201371 (1999)"},{"issue":"3","key":"7_CR6","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0020-0190(00)00093-4","volume":"75","author":"S. Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Segal, M.: Covering a set of points by two axis-parallel boxes. Inf.\u00a0Process.\u00a0Lett.\u00a075(3), 95\u2013100 (2000)","journal-title":"Inf.\u00a0Process.\u00a0Lett."},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.2307\/1968786","volume":"39","author":"H.F. Bohnenblust","year":"1938","unstructured":"Bohnenblust, H.F.: Convex regions and projections in Minkowski spaces. Ann. Math.\u00a039, 301\u2013308 (1938)","journal-title":"Ann. Math."},{"key":"7_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59237-9","volume-title":"Excursions into Combinatorial Geometry","author":"V. Boltyanski","year":"1997","unstructured":"Boltyanski, V., Martini, H., Soltan, P.S.: Excursions into Combinatorial Geometry. Springer, Heidelberg (1997)"},{"key":"7_CR9","first-page":"131","volume-title":"Mathematics \u2013 Key Technology for the Future. Joint Projects between Universities and Industry 2004-2007","author":"R. Brandenberg","year":"2008","unstructured":"Brandenberg, R., Gerken, T., Gritzmann, P., Roth, L.: Modeling and optimization of correction measures for human extremities. In: J\u00e4ger, W., Krebs, H.-J. (eds.) Mathematics \u2013 Key Technology for the Future. Joint Projects between Universities and Industry 2004-2007, pp. 131\u2013148. Springer, Heidelberg (2008)"},{"key":"7_CR10","unstructured":"Brandenberg, R., Roth, L.: Optimal containment under homothetics, a practical approach (submitted, 2007)"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc.\u00a034th Annu.\u00a0ACM Symp.\u00a0Theor.\u00a0Comput., pp. 250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"key":"7_CR12","unstructured":"Bunschoten, R.: A fully vectorized function that computes the Euclidean distance matrix between two sets of vectors (1999), http:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/loadFile.do?objectId=71"},{"issue":"3","key":"7_CR13","first-page":"189","volume":"13","author":"T.M. Chan","year":"1999","unstructured":"Chan, T.M.: More planar two-center algorithms. Comp.\u00a0Geom.\u00a0Theor.\u00a0Appl.\u00a013(3), 189\u2013198 (1999)","journal-title":"Comp.\u00a0Geom.\u00a0Theor.\u00a0Appl."},{"key":"7_CR14","unstructured":"Eppstein, D.: Faster construction of planar two-centers. In: Proc. 8th ACM-SIAM Symp. Discrete Alg., pp. 131\u2013138 (1997)"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T.F. Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput.\u00a0Sci.\u00a038, 293\u2013306 (1985)","journal-title":"Theor. Comput.\u00a0Sci."},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF02187841","volume":"7","author":"P. Gritzmann","year":"1992","unstructured":"Gritzmann, P., Klee, V.: Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput.\u00a0Geom.\u00a07, 255\u2013280 (1992)","journal-title":"Discrete Comput.\u00a0Geom."},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0012-365X(94)00111-U","volume":"136","author":"P. Gritzmann","year":"1994","unstructured":"Gritzmann, P., Klee, V.: On the complexity of some basic problems in computational convexity I: Containment problems. Discrete Math.\u00a0136, 129\u2013174 (1994)","journal-title":"Discrete Math."},{"issue":"1","key":"7_CR18","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1006\/jagm.2001.1194","volume":"42","author":"D. Halperin","year":"2002","unstructured":"Halperin, D., Sharir, M., Goldberg, K.: The 2-center problem with obstacles. J.\u00a0Alg.\u00a042(1), 109\u2013134 (2002)","journal-title":"J.\u00a0Alg."},{"key":"7_CR19","series-title":"Wiley series in probability and mathematical statistics","volume-title":"Clustering algorithms","author":"J.A. Hartigan","year":"1975","unstructured":"Hartigan, J.A.: Clustering algorithms. Wiley series in probability and mathematical statistics. John Wiley and Sons, New York (1975)"},{"key":"7_CR20","first-page":"175","volume":"32","author":"E. Helly","year":"1923","unstructured":"Helly, E.: \u00dcber Mengen konvexer K\u00f6rper mit gemeinschaftlichen Punkten. Jahresbericht Deutsch.\u00a0Math.\u00a0Verein\u00a032, 175\u2013176 (1923)","journal-title":"Jahresbericht Deutsch.\u00a0Math.\u00a0Verein"},{"issue":"1","key":"7_CR21","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0190(93)90153-Z","volume":"47","author":"J. Hershberger","year":"1993","unstructured":"Hershberger, J.: A faster algorithm for the two-center decision problem. Inf.\u00a0Process.\u00a0Lett.\u00a047(1), 23\u201329 (1993)","journal-title":"Inf.\u00a0Process.\u00a0Lett."},{"issue":"3","key":"7_CR22","first-page":"150","volume":"31","author":"M. Hoffmann","year":"2005","unstructured":"Hoffmann, M.: A simple linear algorithm for computing rectilinear 3-centers. Comput.\u00a0Geom.\u00a0Theor.\u00a0Appl.\u00a031(3), 150\u2013165 (2005)","journal-title":"Comput.\u00a0Geom.\u00a0Theor.\u00a0Appl."},{"key":"7_CR23","volume-title":"Algorithms for clustering data","author":"A.K. Jain","year":"1988","unstructured":"Jain, A.K., Dubes, R.C.: Algorithms for clustering data. Prentice Hall, Englewood Cliffs (1988)"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Jaromczyk, J.W., Kowaluk, M.: An efficient algorithm for the Euclidean two-center problem. In: Symp.\u00a0Comp.\u00a0Geom, pp. 303\u2013311 (1994)","DOI":"10.1145\/177424.178038"},{"key":"7_CR25","unstructured":"John, F.: Extremum problems with inequalities as subsidiary conditions. In: Courant Anniversary Volume, pp. 187\u2013204. Interscience (1948)"},{"key":"7_CR26","first-page":"241","volume":"123","author":"H.W.E. Jung","year":"1901","unstructured":"Jung, H.W.E.: \u00dcber die kleinste Kugel, die eine r\u00e4umliche Figur einschlie\u00dft. J.\u00a0Reine Angew.\u00a0Math.\u00a0123, 241\u2013257 (1901)","journal-title":"J.\u00a0Reine Angew.\u00a0Math."},{"key":"7_CR27","unstructured":"Kumar, P.: Clustering and reconstructing large data sets. PhD thesis, Department of Computer Science, Stony Brook University (2004)"},{"key":"7_CR28","first-page":"22","volume-title":"Large-Scale Numerical Optimization","author":"O.L. Mangasarian","year":"1990","unstructured":"Mangasarian, O.L., Setiono, R., Wolberg, W.H.: Pattern recognition via linear programming: theory and application to medical diagnosis. In: Coleman, T.F., Li, Y. (eds.) Large-Scale Numerical Optimization, pp. 22\u201331. SIAM, Philadelphia (1990); Computer Sciences TR 878 (1989)"},{"issue":"3\/4","key":"7_CR29","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0747-7171(08)80067-3","volume":"10","author":"N. Megiddo","year":"1990","unstructured":"Megiddo, N.: On the complexity of some geometric problems in unbounded dimension. J.\u00a0Symb.\u00a0Comput.\u00a010(3\/4), 327\u2013334 (1990)","journal-title":"J.\u00a0Symb.\u00a0Comput."},{"key":"7_CR30","unstructured":"P\u00f3lik, I.: Addendum to the sedumi user guide version 1.1. Technical report, Advanced Optimization Laboratory, McMaster University (2005)"},{"key":"7_CR31","unstructured":"Procopiuc, C.M.: Clustering problems and their applications: A survey. Department of Computer Science, Duke University (1997)"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"Sharir, M.: A near-linear algorithm for the planar 2-center problem. In: Proc. Symp.\u00a0Comp.\u00a0Geom., pp. 106\u2013112 (1996)","DOI":"10.1145\/237218.237251"},{"key":"7_CR33","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11-12","author":"J.F. Sturm","year":"1999","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim.\u00a0Method.\u00a0Softw.\u00a011-12, 625\u2013653 (1999)","journal-title":"Optim.\u00a0Method.\u00a0Softw."},{"key":"7_CR34","unstructured":"del Val, A.: On 2-SAT and renamable Horn. In: Proc.\u00a017th Nat.\u00a0Conf.\u00a0on Artif.\u00a0Intel. AAAI \/ MIT Press (2000)"},{"key":"7_CR35","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1093\/imaman\/dpl009","volume":"17","author":"H. Wei","year":"2006","unstructured":"Wei, H., Murray, A.T., Xiao, N.: Solving the continuous space p-centre problem: planning application issues. IMA J.\u00a0Management Math.\u00a017, 413\u2013425 (2006)","journal-title":"IMA J.\u00a0Management Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:21:56Z","timestamp":1606184516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}