Computer Science – Networking and Internet Architecture
Scientific paper
2008-07-21
Computer Science
Networking and Internet Architecture
Scientific paper
In highly distributed Internet measurement systems distributed agents periodically measure the Internet using a tool called {\tt traceroute}, which discovers a path in the network graph. Each agent performs many traceroute measurement to a set of destinations in the network, and thus reveals a portion of the Internet graph as it is seen from the agent locations. In every period we need to check whether previously discovered edges still exist in this period, a process termed {\em validation}. For this end we maintain a database of all the different measurements performed by each agent. Our aim is to be able to {\em validate} the existence of all previously discovered edges in the minimum possible time. In this work we formulate the validation problem as a generalization of the well know set cover problem. We reduce the set cover problem to the validation problem, thus proving that the validation problem is ${\cal NP}$-hard. We present a $O(\log n)$-approximation algorithm to the validation problem, where $n$ in the number of edges that need to be validated. We also show that unless ${\cal P = NP}$ the approximation ratio of the validation problem is $\Omega(\log n)$.
Gonen Mira
Shavitt Yuval
No associations
LandOfFree
An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership 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 An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-73081