An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem

References

• Agarwal P., Har-Peled S., Varadarajan K., Goodman J. E., Pach J., Wezl E. Geometric approximations via coresets. Combinatorial and Computational Geometry (2005) 52(Cambridge University Press, New York) 1–30Google Scholar
• Bădoiu M., Clarkson K. L. Smaller core-sets for balls. Proc. 14th Annual Sympos. Discrete Algorithms (2003) Baltimore(SIAM, Philadelphia) 801–802Google Scholar
• Bădoiu M., Clarkson K. L. Optimal core-sets for balls. Computational Geometry: Theory Appl. (2008) 40(1):14–22Crossref, Google Scholar
• Bădoiu M., Har-Peled S., Indyk P. Approximate clustering via core-sets. Proc. 34th Annual ACM Sympos. Theory Comput. (2002) Quebec(ACM, New York) 250–257Crossref, Google Scholar
• Blum L., Shub M., Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. (1989) 21(1):1–46Crossref, Google Scholar
• Chandrasekaran R. The weighted Euclidean 1-center problem. Oper. Res. Lett. (1982) 1(3):111–112Crossref, Google Scholar
• Clarkson K. L. Coresets, sparse greeedy approximation, and the Franke-Wolfe algorithm. Proc. 19th Ann. ACM-SIAM Sympos. Discrete Algorithms (2008) San Francisco:922–931Google Scholar
• Drezner Z., Gavish B. ε-Approximations for multidimensional weighted location problems. Oper. Res. (1985) 33(4):772–783Link, Google Scholar
• Dyer M. E. On a multidimensional search technique and its application to the Euclidean one-centre problem. SIAM J. Comput. (1986) 15(3):725–738Crossref, Google Scholar
• Francis R. L. Some aspects of a minimax location problem. Oper. Res. (1967) 15(6):1163–1169Link, Google Scholar
• Frank M., Wolfe P. An algorithm for quadratic programming. Naval Res. Logist. Quart. (1956) 3(1–2):95–110Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics (1988) 2(Springer-Verlag, Berlin) Crossref, Google Scholar
• Hansen P., Peeters D., Richard D., Thisse J.-F. The minisum and minimax location problems revisited. Oper. Res. (1985) 33(6):1251–1265Link, Google Scholar
• Hearn D. W., Vijay J. Efficient algorithms for the (weighted) minimum circle problem. Oper. Res. (1982) 30(4):777–795Link, Google Scholar
• Kumar P., Yıldırım E. A. Minimum-volume enclosing ellipsoids and core sets. J. Optim. Theory Appl. (2005) 126(1):1–21Crossref, Google Scholar
• Kumar P., Mitchell J. S. B., Yıldırım E. A. Approximate minimum enclosing balls in high dimensions using core-sets. ACM J. Experiment. Algorithmics (2003) 8:Article 1.1Crossref, Google Scholar
• Megiddo N. The weighted Euclidean 1-center problem. Math. Oper. Res. (1983) 8(4):498–504Link, Google Scholar
• Megiddo N. On the ball spanned by balls. Discrete Comput. Geometry (1989) 4(6):605–610Crossref, Google Scholar
• Todd M. J., Yıldırım E. A. On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids. Discrete Appl. Math. (2007) 155(13):1731–1744Crossref, Google Scholar
• Tsang I., Kwok J., Cheung P.-M., Cowell R. G., Ghahramani Z. Very large SVM training using core vector machines. Proc. 10th Internat. Workshop on Artificial Intelligence Statist. (2005) Barbados(Society for Artificial Intelligence and Statistics, Hoboken, NJ) 349–356 http://www.gatsby.ucl.ac.uk/aistats/fullpapers/172.pdfGoogle Scholar
• Wolfe P., Abadie J. Convergence theory in nonlinear programming. Integer and Nonlinear Programming (1970) (North-Holland, Amsterdam) 1–36Google Scholar
• Yıldırım E. A. Two algorithms for the minimum enclosing ball problem. SIAM J. Optim. (2008) 19(3):1368–1391Crossref, Google Scholar
• Zhou G., Toh K. C., Sun B. Efficient algorithms for the smallest enclosing ball problem. Computational Optim. Appl. (2005) 30(2):147–160Crossref, Google Scholar