{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,13]],"date-time":"2025-09-13T15:43:54Z","timestamp":1757778234465},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T00:00:00Z","timestamp":1597276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T00:00:00Z","timestamp":1597276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N509449\/1"],"award-info":[{"award-number":["EP\/N509449\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN Oper. Res. Forum"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>As the main problem, we consider covering of a<jats:italic>d<\/jats:italic>-dimensional cube by<jats:italic>n<\/jats:italic>balls with reasonably large<jats:italic>d<\/jats:italic>(10 or more) and reasonably small<jats:italic>n<\/jats:italic>, like<jats:italic>n<\/jats:italic>= 100 or<jats:italic>n<\/jats:italic>= 1000. We do not require the full coverage but only 90% or 95% coverage. We establish that efficient covering schemes have several important properties which are not seen in small dimensions and in asymptotical considerations, for very large<jats:italic>n<\/jats:italic>. One of these properties can be termed \u2018do not try to cover the vertices\u2019 as the vertices of the cube and their close neighbourhoods are very hard to cover and for large<jats:italic>d<\/jats:italic>there are far too many of them. We clearly demonstrate that, contrary to a common belief, placing balls at points which form a low-discrepancy sequence in the cube, results in a very inefficient covering scheme. For a family of random coverings, we are able to provide very accurate approximations to the coverage probability. We then extend our results to the problems of coverage of a cube by smaller cubes and quantization, the latter being also referred to as facility location. Along with theoretical considerations and derivation of approximations, we provide results of a large-scale numerical investigation.<\/jats:p>","DOI":"10.1007\/s43069-020-0015-8","type":"journal-article","created":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T04:38:48Z","timestamp":1597293528000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Covering of High-Dimensional Cubes and Quantization"],"prefix":"10.1007","volume":"1","author":[{"given":"Anatoly","family":"Zhigljavsky","sequence":"first","affiliation":[]},{"given":"Jack","family":"Noonan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,13]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108755528","volume-title":"Foundations of data science","author":"A Blum","year":"2020","unstructured":"Blum A, Hopcroft J, Kannan R (2020) Foundations of data science. Cambridge University Press, Cambridge"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02399201","volume":"156","author":"S Janson","year":"1986","unstructured":"Janson S (1986) Random coverings in several dimensions. Acta Mathematica 156:83\u2013118","journal-title":"Acta Mathematica"},{"issue":"4","key":"15_CR3","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF02574390","volume":"12","author":"J Januszewski","year":"1994","unstructured":"Januszewski J, Lassak M (1994) On-line covering the unit cube by cubes. Discrete Comput Geom 12(4):433\u2013438","journal-title":"Discrete Comput Geom"},{"issue":"5","key":"15_CR4","doi-asserted-by":"publisher","first-page":"2635","DOI":"10.1137\/070709359","volume":"30","author":"S Joe","year":"2008","unstructured":"Joe S, Kuo FY (2008) Constructing Sobol sequences with better two-dimensional projections. SIAM J Sci Comput 30(5):2635\u20132654","journal-title":"SIAM J Sci Comput"},{"issue":"2","key":"15_CR5","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0378-3758(90)90122-B","volume":"26","author":"ME Johnson","year":"1990","unstructured":"Johnson ME, Moore LM, Ylvisaker D (1990) Minimax and maximin distance designs. J Stat Plan Infer 26(2):131\u2013148","journal-title":"J Stat Plan Infer"},{"issue":"1","key":"15_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02574367","volume":"12","author":"W Kuperberg","year":"1994","unstructured":"Kuperberg W (1994) On-line covering a cube by a sequence of cubes. Discrete Comput Geom 12(1):83\u201390","journal-title":"Discrete Comput Geom"},{"issue":"1","key":"15_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.3923\/ajms.2011.66.70","volume":"4","author":"S Li","year":"2011","unstructured":"Li S (2011) Concise formulas for the area and volume of a hyperspherical cap. Asian J Math Stat 4(1):66\u201370","journal-title":"Asian J Math Stat"},{"key":"15_CR8","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970081","volume-title":"Random number generation and quasi-Monte Carlo methods","author":"H Niederreiter","year":"1992","unstructured":"Niederreiter H (1992) Random number generation and quasi-Monte Carlo methods. SIAM, Philadelphia"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Noonan J, Zhigljavsky A (2021) Non-lattice covering and quantization in high dimensions. In: Black Box Optimization, Machine Learning and No-Free Lunch Theorems. Springer","DOI":"10.1007\/978-3-030-66515-9_10"},{"key":"15_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65809-9","volume-title":"Sums of independent random variables","author":"VV Petrov","year":"1975","unstructured":"Petrov VV (1975) Sums of independent random variables. Springer, Berlin"},{"key":"15_CR11","volume-title":"Limit theorems of probability theory: sequences of independent random variables","author":"VV Petrov","year":"1995","unstructured":"Petrov VV (1995) Limit theorems of probability theory: sequences of independent random variables. Oxford Science, Oxford"},{"key":"15_CR12","volume-title":"Asymptotic theory of statistical inference","author":"BLS Prakasa Rao","year":"1987","unstructured":"Prakasa Rao BLS (1987) Asymptotic theory of statistical inference. Wiley, New York"},{"issue":"3","key":"15_CR13","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/s11222-011-9242-3","volume":"22","author":"L Pronzato","year":"2012","unstructured":"Pronzato L, M\u00fcller W. G. (2012) Design of computer experiments: space filling and beyond. Stat Comput 22(3):681\u2013701","journal-title":"Stat Comput"},{"key":"15_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-2759-2","volume-title":"Minimax models in the theory of numerical methods","author":"A Sukharev","year":"1992","unstructured":"Sukharev A (1992) Minimax models in the theory of numerical methods. Springer Science & Business Media, Berlin"},{"key":"15_CR15","unstructured":"Tibken B, Constales D, et al. (1997) The volume of the intersection of a concentric cube and ball in n-dimensional space: collection of approximations. In: SIAM Review, vol 39, pp 783\u2013786"},{"key":"15_CR16","unstructured":"T\u00f3th GF (2017) Packing and covering Handbook of discrete and computational geometry. Chapman and Hall, London, pp 27\u201366"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"T\u00f3th GF, Kuperberg W (1993) Packing and covering with convex sets. In: Handbook of Convex Geometry. Elsevier, pp 799\u2013860","DOI":"10.1016\/B978-0-444-89597-4.50007-X"},{"key":"15_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-3436-1","volume-title":"Theory of global random search","author":"A Zhigljavsky","year":"1991","unstructured":"Zhigljavsky A (1991) Theory of global random search. Kluwer, Norwell"},{"key":"15_CR19","volume-title":"Stochastic global optimization","author":"A Zhigljavsky","year":"2007","unstructured":"Zhigljavsky A, Zilinskas A (2007) Stochastic global optimization. Springer Science & Business Media, Berlin"},{"issue":"8","key":"15_CR20","doi-asserted-by":"publisher","first-page":"1921","DOI":"10.1007\/s11590-012-0547-8","volume":"7","author":"A \u017eilinskas","year":"2013","unstructured":"\u017eilinskas A (2013) On the worst-case optimal multi-objective global optimization. Optim Lett 7(8):1921\u20131928","journal-title":"Optim Lett"}],"container-title":["SN Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-0015-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-020-0015-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-0015-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T19:52:28Z","timestamp":1667764348000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-020-0015-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,13]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["15"],"URL":"https:\/\/doi.org\/10.1007\/s43069-020-0015-8","relation":{},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,13]]},"assertion":[{"value":"24 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interest"}}],"article-number":"18"}}