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

Conference paper

Authors: Matti Åstrand and Jukka Suomela
Title: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
Conference: 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Santorini, Greece, June 2010
Proceedings: Friedhelm Meyer auf der Heide and Cynthia 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 Press, New York, NY, USA, 2010
ISBN: 978-1-4503-0079-7
pages 294–302
doi:10.1145/1810479.1810533
Links: publisher’s version · free access · authors’ version
© ACM 2010 — 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
presentation, 15 June 2010
presentation at HIIT seminar, 16 October 2009
presentation at the University of Paderborn, 20 October 2009
presentation at Finite Model Theory seminar, 26 February 2010
presentation at ETH Zurich, 2 March 2010
presentation at TU Braunschweig, 29 November 2010
conference · proceedings · DBLP
Abstract:
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.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.