{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:19Z","timestamp":1740109579286,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,3,31]],"date-time":"2020-03-31T00:00:00Z","timestamp":1585612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,31]],"date-time":"2020-03-31T00:00:00Z","timestamp":1585612800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_150055 \/ 1"],"award-info":[{"award-number":["200021_150055 \/ 1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00454-020-00193-0","type":"journal-article","created":{"date-parts":[[2020,3,31]],"date-time":"2020-03-31T16:17:58Z","timestamp":1585671478000},"page":"700-733","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Random Sampling with Removal"],"prefix":"10.1007","volume":"64","author":[{"given":"Kenneth L.","family":"Clarkson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernd","family":"G\u00e4rtner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"May","family":"Szedl\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,31]]},"reference":[{"issue":"1","key":"193_CR1","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF01582137","volume":"61","author":"I Adler","year":"1993","unstructured":"Adler, I., Shamir, R.: A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio. Math. Program. 61(1), 39\u201352 (1993)","journal-title":"Math. Program."},{"issue":"3","key":"193_CR2","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02574379","volume":"12","author":"N Amenta","year":"1994","unstructured":"Amenta, N.: Helly-type theorems and generalized linear programming. Discrete Comput. Geom. 12(3), 241\u2013261 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"193_CR3","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.comgeo.2010.09.003","volume":"44","author":"Y Brise","year":"2011","unstructured":"Brise, Y., G\u00e4rtner, B.: Clarkson\u2019s algorithm for violator spaces. Comput. Geom. 44(2), 70\u201381 (2011)","journal-title":"Comput. Geom."},{"issue":"1","key":"193_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-003-0499-y","volume":"102","author":"GC Calafiore","year":"2005","unstructured":"Calafiore, G.C., Campi, M.C.: Uncertain convex programs: randomized solutions and confidence levels. Math. Program. 102(1), 25\u201346 (2005)","journal-title":"Math. Program."},{"issue":"5","key":"193_CR5","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1109\/TAC.2006.875041","volume":"51","author":"GC Calafiore","year":"2006","unstructured":"Calafiore, G.C., Campi, M.C.: The scenario approach to robust control design. IEEE Trans. Autom. Control 51(5), 742\u2013753 (2006)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"3","key":"193_CR6","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1137\/07069821X","volume":"19","author":"MC Campi","year":"2008","unstructured":"Campi, M.C., Garatti, S.: The exact feasibility of randomized solutions of uncertain convex programs. SIAM J. Optim. 19(3), 1211\u20131230 (2008)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"193_CR7","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s10957-010-9754-6","volume":"148","author":"MC Campi","year":"2011","unstructured":"Campi, M.C., Garatti, S.: A sampling-and-discarding approach to chance-constrained optimization: feasibility and optimality. J. Optim. Theory Appl. 148(2), 257\u2013280 (2011)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"193_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2(2), 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"193_CR9","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: A Las Vegas algorithm for linear programming when the dimension is small. In: Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 452\u2013456. IEEE (1988)","DOI":"10.1109\/SFCS.1988.21961"},{"issue":"4","key":"193_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF02573988","volume":"10","author":"KL Clarkson","year":"1993","unstructured":"Clarkson, K.L.: A bound on local minima of arrangements that implies the upper bound theorem. Discrete Comput. Geom. 10(4), 427\u2013433 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"193_CR11","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"KL Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. Assoc. Comput. Mach. 42(2), 488\u2013499 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"193_CR12","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"KL Clarkson","year":"1993","unstructured":"Clarkson, K.L., Mehlhorn, K., Seidel, R.: Four results on randomized incremental constructions. Comput. Geom. 3(4), 185\u2013212 (1993)","journal-title":"Comput. Geom."},{"issue":"5","key":"193_CR13","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry II. Discrete Comput. Geom. 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"193_CR14","unstructured":"Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms. MIT Electrical Engineering and Computer Science Series. MIT Press, Cambridge (1990)"},{"issue":"1","key":"193_CR15","first-page":"201","volume":"25","author":"JA De Loera","year":"2018","unstructured":"De Loera, J.A., La Haye, R.N., Oliveros, D., Rold\u00e1n-Pensado, E.: Chance-constrained convex mixed-integer optimization and beyond: two sampling algorithms within $$S$$-optimization. J. Convex Anal. 25(1), 201\u2013218 (2018)","journal-title":"J. Convex Anal."},{"issue":"2","key":"193_CR16","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01587088","volume":"44","author":"ME Dyer","year":"1989","unstructured":"Dyer, M.E., Frieze, A.M.: A randomized algorithm for fixed-dimensional linear programming. Math. Program. 44(2), 203\u2013212 (1989)","journal-title":"Math. Program."},{"key":"193_CR17","unstructured":"Fagiano, L., Schildbach, G.: Sampling lemma with a-posteriori sample removal (2013). Unpublished mansuscript"},{"issue":"4\u20135","key":"193_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1142\/S0218195904001500","volume":"14","author":"K Fischer","year":"2004","unstructured":"Fischer, K., G\u00e4rtner, B.: The smallest enclosing ball of balls: combinatorial structure and algorithms. Int. J. Comput. Geom. Appl. 14(4\u20135), 341\u2013378 (2004)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"193_CR19","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B.: A subexponential algorithm for abstract optimization problems. In: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pp. 464\u2013472. IEEE (1992)","DOI":"10.1109\/SFCS.1992.267805"},{"issue":"2","key":"193_CR20","first-page":"93","volume":"6","author":"B G\u00e4rtner","year":"2015","unstructured":"G\u00e4rtner, B.: Sampling with removal in LP-type problems. J. Comput. Geom. 6(2), 93\u2013112 (2015)","journal-title":"J. Comput. Geom."},{"issue":"11","key":"193_CR21","doi-asserted-by":"publisher","first-page":"2124","DOI":"10.1016\/j.dam.2007.08.048","volume":"156","author":"B G\u00e4rtner","year":"2008","unstructured":"G\u00e4rtner, B., Matou\u0161ek, J., R\u00fcst, L., \u0160kovro\u0148, P.: Violator spaces: structure and algorithms. Discrete Appl. Math. 156(11), 2124\u20132141 (2008)","journal-title":"Discrete Appl. Math."},{"key":"193_CR22","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., Schurr, I.: Linear programming and unique sink orientations. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 749\u2013757. ACM, New York (2006)","DOI":"10.1145\/1109557.1109639"},{"key":"193_CR23","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., Welzl, E.: Linear programming \u2013 randomization and abstract frameworks. Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science (Grenoble, 1996). Lecture Notes in Computer Science, vol. 1046, pp. 667\u2013687. Springer, Berlin (1996)","DOI":"10.1007\/3-540-60922-9_54"},{"issue":"4","key":"193_CR24","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00454-001-0006-2","volume":"25","author":"B G\u00e4rtner","year":"2001","unstructured":"G\u00e4rtner, B., Welzl, E.: A simple sampling lemma: analysis and applications in geometric optimization. Discrete Comput. Geom. 25(4), 569\u2013590 (2001)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"193_CR25","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\epsilon $$-Nets and simplex range queries. Discrete Comput. Geom. 2(2), 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"193_CR26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Statist. Assoc. 58, 13\u201330 (1963)","journal-title":"J. Am. Statist. Assoc."},{"key":"193_CR27","doi-asserted-by":"crossref","unstructured":"Kalai, G.: A subexponential randomized simplex algorithm. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 475\u2013482 (1992)","DOI":"10.1145\/129712.129759"},{"issue":"4","key":"193_CR28","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s00454-008-9085-7","volume":"42","author":"J Matou\u0161ek","year":"2009","unstructured":"Matou\u0161ek, J.: Removing degeneracy in LP-type problems revisited. Discrete Comput. Geom. 42(4), 517\u2013526 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"4\u20135","key":"193_CR29","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16(4\u20135), 498\u2013516 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"193_CR30","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. Assoc. Comput. Mach. 31(1), 114\u2013127 (1984)","journal-title":"J. Assoc. Comput. Mach."},{"key":"193_CR31","volume-title":"Handbook of Discrete and Computational Geometry, chapter 47. Discrete Mathematics and its Applications","author":"NH Mustafa","year":"2018","unstructured":"Mustafa, N.H., Varadarajan, K.: Epsilon-approximations & epsilon-nets. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, chapter 47. Discrete Mathematics and its Applications. CRC Press, Boca Raton (2018)"},{"issue":"9","key":"193_CR32","doi-asserted-by":"publisher","first-page":"3637","DOI":"10.1073\/pnas.74.9.3637","volume":"74","author":"HE Scarf","year":"1977","unstructured":"Scarf, H.E.: An observation on the structure of production sets with indivisibilities. Proc. Nat. Acad. Sci. USA 74(9), 3637\u20133641 (1977)","journal-title":"Proc. Nat. Acad. Sci. USA"},{"issue":"5","key":"193_CR33","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R Seidel","year":"1991","unstructured":"Seidel, R.: Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom. 6(5), 423\u2013434 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"193_CR34","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (Cachan, 1992), pp. 569\u2013579, Lecture Notes in Computer Science, vol. 577. Springer, Berlin (1992)","DOI":"10.1007\/3-540-55210-3_213"},{"key":"193_CR35","unstructured":"\u0160kovro\u0148, P.: Abstract Models of Optimization Problems. PhD thesis, Charles University, Prague (2007). https:\/\/is.cuni.cz\/webapps\/zzp\/detail\/43007\/?lang=en"},{"key":"193_CR36","unstructured":"Szedl\u00e1k, M.: Redundancy in Linear Systems: Combinatorics, Algorithms and Analysis. PhD thesis, ETH Z\u00fcrich, Z\u00fcrich (2017). https:\/\/doi.org\/10.3929\/ethz-b-000167108"},{"key":"193_CR37","doi-asserted-by":"crossref","unstructured":"Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: New Results and New Trends in Computer Science (Graz, 1991). Lecture Notes in Comput. Sci., vol. 555, pp. 359\u2013370. Springer, Berlin (1991)","DOI":"10.1007\/BFb0038202"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00193-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-020-00193-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00193-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,30]],"date-time":"2021-03-30T23:36:26Z","timestamp":1617147386000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-020-00193-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,31]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["193"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00193-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,3,31]]},"assertion":[{"value":"28 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}