The covert set-cover problem with application to Network Discovery

Details The covert set-cover problem with application to Network Discovery The covert set-cover problem with application to Network Discovery

2012-02-06

arxiv.org/abs/1202.1090v1

Computer Science

Data Structures and Algorithms

Scientific paper

We address a version of the set-cover problem where we do not know the sets initially (and hence referred to as covert) but we can query an element to find out which sets contain this element as well as query a set to know the elements. We want 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$ within $O(\log N)$ factor with high probability using $O(OPT \cdot \log^2 N)$ queries where $N$ is the input size. We apply this technique to the network discovery problem that involves certifying all the edges and non-edges of an unknown $n$-vertices graph based on layered-graph queries from a minimal number of vertices. By reducing it to the covert set-cover problem we present an $O(\log^2 n)$-competitive Monte Carlo randomized algorithm for the covert version of network discovery problem. The previously best known algorithm has a competitive ratio of $\Omega (\sqrt{n\log n})$ and therefore our result achieves an exponential improvement.

Affiliated with

Also associated with

No associations

Rating

The covert set-cover problem with application to Network Discovery does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The covert set-cover problem with application to Network Discovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The covert set-cover problem with application to Network Discovery will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-119211