The Covert Set Cover Problem with Applications to Network Discovery§
Sandeep Sen, V. N. Muralidhara · Revista de Fomento Social · 2014
me n t a s we l l a s q u e r y a s e t t o k n o w t h e e l e me n t s .We wa n t to find a small set-cover using a minimal number of such queries.We present a Monte Carlo randomized algorithm that approximates an optimal set-cover of size OPT w i t h i n O(log N) factor with high probability using O(OPT .log 2 N) queries wh e r e N is the input size.