Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
Permalänk
Citation
Åstrand , M & Suomela , J 2010 , Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks . in F Meyer auf der Heide & C A Phillips (eds) , SPAA’10 : Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures, June 13–15, 2010. Thira, Santorini, Greece . ACM , pp. 294–302 , ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , Santorini , Greece , 13/06/2010 . https://doi.org/10.1145/1810479.1810533
| Titel: | Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks |
| Författare: | Åstrand, Matti; Suomela, Jukka |
| Medarbetare: |
Meyer auf der Heide, Friedhelm
Phillips, Cynthia A. |
| Upphovmannens organisation: | Helsinki Institute for Information Technology Department of Computer Science |
| Utgivare: | ACM |
| Datum: | 2010 |
| Språk: | eng |
| Sidantal: | 9 |
| Tillhör serie: | SPAA’10 |
| ISBN: | 978-1-4503-0079-7 |
| DOI: | https://doi.org/10.1145/1810479.1810533 |
| Permanenta länken (URI): | http://hdl.handle.net/10138/27922 |
| Abstrakt: | 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. |
| Subject: | 113 Computer and information sciences |
| Referentgranskad: | Ja |
| Användningsbegränsning: | openAccess |
| Parallelpublicerad version: | acceptedVersion |
Filer under denna titel
Totalt antal nerladdningar: Laddar...
| Filer | Storlek | Format | Granska |
|---|---|---|---|
| spaa_2010_paper.pdf | 411.8Kb | Granska/Öppna |
Detta dokument registreras i samling:
-
TUHAT-artikkelit [50254]