An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership
| dc.creator | Gonen, Mira | |
| dc.creator | Shavitt, Yuval | |
| dc.date | 2008-07-21 | |
| dc.date.accessioned | 2026-07-07T09:51:53Z | |
| dc.date.available | 2026-07-07T09:51:53Z | |
| dc.description | 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 $Ω(\log n)$. | |
| dc.identifier | https://arxiv.org/abs/0807.3326 | |
| dc.identifier | http://arxiv.org/abs/0807.3326 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/165401 | |
| dc.subject | Networking and Internet Architecture | |
| dc.subject | Computational Complexity | |
| dc.title | An $O(\log n)$-approximation for the Set Cover Problem with Set Ownership | |
| dc.type | text |