Covering of high-dimensional cubes and quantization

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 3 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item