Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
| Contribuinte(s) |
University of Helsinki, Helsinki Institute for Information Technology HIIT |
|---|---|
| Data(s) |
2010
|
| Resumo |
We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks. |
| Formato |
9 |
| Identificador | |
| Idioma(s) |
eng |
| Relação |
SPAA’10 Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures, June 13–15, 2010. Thira, Santorini, Greece |
| Direitos |
This is the authors’ version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proc. 22nd ACM Symposium on Parallelism in Algorithms and Architectures. http://doi.acm.org/10.1145/1810479.1810533 |
| Fonte |
Åstrand , M & Suomela , J 2010 , ' Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks ' in SPAA’10 : Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures, June 13–15, 2010. Thira, Santorini, Greece , pp. 294–302 . , 10.1145/1810479.1810533 |
| Palavras-Chave | #113 Computer and information sciences |
| Tipo |
A4 Article in conference publication (refereed) info:eu-repo/semantics/conferencePaper info:eu-repo/semantics/acceptedVersion |
