An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership

Mira Gonen, Yuval Shavitt

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…