Zhigljavsky, Anatoly ORCID: https://orcid.org/0000-0003-0630-8279 and Noonan, Jack 2020. Covering of high-dimensional cubes and quantization. SN Operations Research Forum 1 (3) , 18. 10.1007/s43069-020-0015-8 |
PDF
- Published Version
Available under License Creative Commons Attribution. Download (3MB) |
Abstract
As the main problem, we consider covering of a d-dimensional cube by n balls with reasonably large d (10 or more) and reasonably small n, like n = 100 or n = 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 n. One of these properties can be termed ‘do not try to cover the vertices’ as the vertices of the cube and their close neighbourhoods are very hard to cover and for large d 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.
Item Type: | Article |
---|---|
Date Type: | Published Online |
Status: | Published |
Schools: | Mathematics |
ISSN: | 2662-2556 |
Date of First Compliant Deposit: | 19 August 2020 |
Date of Acceptance: | 14 May 2020 |
Last Modified: | 04 May 2023 19:22 |
URI: | https://orca.cardiff.ac.uk/id/eprint/134282 |
Citation Data
Cited 5 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
Edit Item |