{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T16:55:39Z","timestamp":1792947339743,"version":"4.5.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,12,4]],"date-time":"2012-12-04T00:00:00Z","timestamp":1354579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,5]]},"DOI":"10.1007\/s00453-012-9721-8","type":"journal-article","created":{"date-parts":[[2012,12,3]],"date-time":"2012-12-03T22:08:39Z","timestamp":1354572519000},"page":"148-183","source":"Crossref","is-referenced-by-count":49,"title":["On the Least Trimmed Squares Estimator"],"prefix":"10.1007","volume":"69","author":[{"given":"David M.","family":"Mount","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan S.","family":"Netanyahu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christine D.","family":"Piatko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruth","family":"Silverman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Angela Y.","family":"Wu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,12,4]]},"reference":[{"key":"9721_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (2000)"},{"key":"9721_CR2","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I. Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., Patrascu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50, 584\u2013596 (2008)","journal-title":"Algorithmica"},{"key":"9721_CR3","series-title":"Springer LNCS","first-page":"697","volume-title":"Proc. Intl. Conf. on Computational Science and Its Applications","author":"T. Bernholt","year":"2005","unstructured":"Bernholt, T.: Computing the least median of squares estimator in time O(n d ). In: Proc. Intl. Conf. on Computational Science and Its Applications. Springer LNCS, vol. 3480, pp. 697\u2013706. Springer, Berlin (2005)"},{"key":"9721_CR4","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/s11222-008-9054-2","volume":"18","author":"D. Bremner","year":"2008","unstructured":"Bremner, D., Chen, D., Iacono, J., Langerman, S., Morin, P.: Output-sensitive algorithms for Tukey depth and related problems. Stat. Comput. 18, 259\u2013266 (2008)","journal-title":"Stat. Comput."},{"key":"9721_CR5","first-page":"430","volume-title":"Proc. 15th Annu. ACM-SIAM Sympos. Discrete Algorithms","author":"T.M. Chan","year":"2004","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proc. 15th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 430\u2013436 (2004)"},{"key":"9721_CR6","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1080\/01621459.1993.10476352","volume":"88","author":"C.W. Coakley","year":"1993","unstructured":"Coakley, C.W., Hettmansperger, T.P.: A bounded influence, high breakdown, efficient regression estimator. J. Am. Stat. Assoc. 88, 872\u2013880 (1993)","journal-title":"J. Am. Stat. Assoc."},{"key":"9721_CR7","volume-title":"Elementary Numerical Analysis: an Algorithmic Approach","author":"S.D. Conte","year":"1980","unstructured":"Conte, S.D., De Boor, C.W.: Elementary Numerical Analysis: an Algorithmic Approach, 3rd edn. McGraw-Hill, New York (1980)","edition":"3"},{"key":"9721_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9721_CR9","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer, Heidelberg (1987)"},{"key":"9721_CR10","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38, 165\u2013194 (1989). Corrigendum in 42, 249\u2013251 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9721_CR11","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1080\/01621459.1990.10475313","volume":"85","author":"H. Edelsbrunner","year":"1990","unstructured":"Edelsbrunner, H., Souvaine, D.L.: Computing median-of-squares regression lines and guided topological sweep. J. Am. Stat. Assoc. 85, 115\u2013119 (1990)","journal-title":"J. Am. Stat. Assoc."},{"key":"9721_CR12","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. Chic. J. Theor. Comput. Sci. 1999(8) (1999). http:\/\/compgeom.cs.uiuc.edu\/~jeffe\/pubs\/linsat.html"},{"key":"9721_CR13","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s00454-006-1267-6","volume":"36","author":"J. Erickson","year":"2006","unstructured":"Erickson, J., Har-Peled, S., Mount, D.M.: On the least median square problem. Discrete Comput. Geom. 36, 593\u2013607 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"9721_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02574027","volume":"13","author":"J. Erickson","year":"1995","unstructured":"Erickson, J., Seidel, R.: Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput. Geom. 13, 41\u201357 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9721_CR15","unstructured":"Da Fonseca, G.D.: Fitting flats to points with outliers. Unpublished manuscript (2010)"},{"key":"9721_CR16","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A. Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of O(n 2) problems in computational geometry. Comput. Geom. Theory Appl. 5, 165\u2013185 (1995)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9721_CR17","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.comgeo.2006.02.003","volume":"36","author":"S. Har-Peled","year":"2007","unstructured":"Har-Peled, S.: How to get close to the median shape. Comput. Geom. Theory Appl. 36, 39\u201351 (2007)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9721_CR18","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0167-9473(92)00070-8","volume":"17","author":"D.M. Hawkins","year":"1994","unstructured":"Hawkins, D.M.: The feasible solution algorithm for least trimmed squares regression. Comput. Stat. Data Anal. 17, 185\u2013196 (1994)","journal-title":"Comput. Stat. Data Anal."},{"key":"9721_CR19","volume-title":"Topics in Algebra","author":"I.N. Herstein","year":"1975","unstructured":"Herstein, I.N.: Topics in Algebra, 2nd edn. Wiley, New York (1975)","edition":"2"},{"key":"9721_CR20","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0167-9473(95)92697-V","volume":"19","author":"O. H\u00f6ssjer","year":"1995","unstructured":"H\u00f6ssjer, O.: Exact computation of the least trimmed squares estimate in simple linear regression. Comput. Stat. Data Anal. 19, 265\u2013282 (1995)","journal-title":"Comput. Stat. Data Anal."},{"key":"9721_CR21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s00454-003-0011-x","volume":"30","author":"S. Langerman","year":"2003","unstructured":"Langerman, S., Steiger, W.: The complexity of hyperplane depth in the plane. Discrete Comput. Geom. 30, 299\u2013309 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"9721_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, Berlin (2002)"},{"key":"9721_CR23","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1023\/A:1023208625954","volume":"13","author":"K. Miller","year":"2003","unstructured":"Miller, K., Ramaswami, S., Rousseeuw, P., Sellares, T., Souvaine, D., Streinu, I., Struyf, A.: Efficient computation of location depth contours by methods of combinatorial geometry. Stat. Comput. 13, 153\u2013162 (2003)","journal-title":"Stat. Comput."},{"key":"9721_CR24","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1142\/S0218195900000334","volume":"10","author":"D.M. Mount","year":"2000","unstructured":"Mount, D.M., Netanyahu, N.S., Piatko, C., Silverman, R., Wu, A.Y.: Quantile approximation for robust statistical estimation and k-enclosing problems. Int. J. Comput. Geom. Appl. 10, 593\u2013608 (2000)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9721_CR25","unstructured":"Mount, D.M., Netanyahu, N.S., Piatko, C., Silverman, R., Wu, A.Y.: A practical approximation algorithm for the LTS estimator. Technical report CS-TR-5000, University of Maryland (2011)"},{"key":"9721_CR26","doi-asserted-by":"crossref","first-page":"2461","DOI":"10.1016\/j.csda.2006.08.033","volume":"51","author":"D.M. Mount","year":"2007","unstructured":"Mount, D.M., Netanyahu, N.S., Romanik, K.R., Silverman, R., Yu, A.Y.: A practical approximation algorithm for the LMS line estimator. Comput. Stat. Data Anal. 51, 2461\u20132486 (2007)","journal-title":"Comput. Stat. Data Anal."},{"key":"9721_CR27","series-title":"Statistics for Industry and Technology","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-0348-7958-3_19","volume-title":"Theory and Applications of Recent Robust Methods","author":"D.M. Mount","year":"2004","unstructured":"Mount, D.M., Netanyahu, N.S., Zuck, E.: Analyzing the number of samples required for an approximate Monte-Carlo LMS line estimator. In: Hubert, M., Pison, G., Struyf, A., Van Aelst, S. (eds.) Theory and Applications of Recent Robust Methods. Statistics for Industry and Technology, pp. 207\u2013219. Birkh\u00e4user, Basel (2004)"},{"key":"9721_CR28","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1080\/01621459.1984.10477105","volume":"79","author":"P.J. Rousseeuw","year":"1984","unstructured":"Rousseeuw, P.J.: Least median-of-squares regression. J. Am. Stat. Assoc. 79, 871\u2013880 (1984)","journal-title":"J. Am. Stat. Assoc."},{"key":"9721_CR29","doi-asserted-by":"crossref","DOI":"10.1002\/0471725382","volume-title":"Robust Regression and Outlier Detection","author":"P.J. Rousseeuw","year":"1987","unstructured":"Rousseeuw, P.J., Leroy, A.M.: Robust Regression and Outlier Detection. Wiley, New York (1987)"},{"key":"9721_CR30","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10618-005-0024-4","volume":"12","author":"P.J. Rousseeuw","year":"2006","unstructured":"Rousseeuw, P.J., van Driessen, K.: Computing LTS regression for large data sets. Data Min. Knowl. Discov. 12, 29\u201345 (2006)","journal-title":"Data Min. Knowl. Discov."},{"key":"9721_CR31","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1080\/01621459.1992.10475224","volume":"87","author":"D.G. Simpson","year":"1992","unstructured":"Simpson, D.G., Ruppert, D., Carroll, R.J.: On one-step GM estimates and stability of influences in linear regression. J. Am. Stat. Assoc. 87, 439\u2013450 (1992)","journal-title":"J. Am. Stat. Assoc."},{"key":"9721_CR32","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1080\/01621459.1987.10478500","volume":"82","author":"D.L. Souvaine","year":"1987","unstructured":"Souvaine, D.L., Steele, J.M.: Time- and space-efficient algorithms for least median of squares regression. J. Am. Stat. Assoc. 82, 794\u2013801 (1987)","journal-title":"J. Am. Stat. Assoc."},{"key":"9721_CR33","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1214\/aos\/1176350366","volume":"15","author":"V.J. Yohai","year":"1987","unstructured":"Yohai, V.J.: High breakdown-point and high efficiency robust estimates for regression. Ann. Stat. 15, 642\u2013656 (1987)","journal-title":"Ann. Stat."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9721-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9721-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9721-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9721-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,4]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["9721"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9721-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,4]]}}}