Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Covering of high-dimensional cubes and quantization

Zhigljavsky, Anatoly and Noonan, Jack 2020. Covering of high-dimensional cubes and quantization. SN Operations Research Forum 1 (3) , 18. 10.1007/s43069-020-0015-8

[img] 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: 19 Aug 2020 12:00
URI: http://orca.cf.ac.uk/id/eprint/134282

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics