Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

Visa fullständig post



Permalänk

http://hdl.handle.net/10138/27922

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 PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post