Information Retrieval and Dominating Sets

Abstract

The problem studied in this paper is a special case of set membership testing. This problem is defined as storing a single element from a set of m elements, represented as a bit string of optimal length, and answering whether a queried element is the stored one without reading all the stored bits. Damaschke has shown that finding lcube dominating sets in hypercubes is equivalent to finding schemes for membership testing. The specific schemes that he found only serve as proof-of-concept and the problem of optimal schemes is an open question. Our main contribution is numerical improvements on these schemes. The new schemes have primarily been found using the low-dimensional (grid) relaxation that Damaschke introduced, and a branchand- bound search approach.