Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. (English) Zbl 1314.68156
Proceedings of the 24th annual ACM symposium on principles of distributed computing, PODC ’05, Las Vegas, NV, USA, July 17–20, 2005. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-994-2). 118-125 (2005).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W15 | Distributed algorithms |
| 68W25 | Approximation algorithms |
References:
| [1] | R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27-45, 1985. · Zbl 0557.90072 |
| [2] | F. Chudak, T. Erlebach, and A. Panconesi. Primal-dual based distributed algorithms for vertex cover with soft capacities and facility location. Manuscript, 2004. |
| [3] | J. Chuzhoy and J. Naor. Covering problems with hard capacities. In Proceedings, IEEE Symposium on Foundations of Computer Science, pages 481-489, 2002. |
| [4] | D. Dubhashi, O. Häggström, G. Mambrini, A. Panconesi, and C. Petrioli. Blue pleieades, a new solution for device discovery and scatternet formation in multi-hop bluetooth networks. To appear in ACM Wireless Networks. 10.1007/s11276-006-1304-7 |
| [5] | U. Feige. A threshold of ln n for approximating set cover. In Proceedings, ACM Symposium on Theory of Computing, pages 314-318, 1996. 10.1145/237814.237977 · Zbl 0922.68067 |
| [6] | R. Gandhi, E. Halperin, S. Khuller, G. Kortsarz, and A. Srinivasan. An improved approximation algorithm for vertex cover with hard capacities (extended abstract). In Proceedings, International Colloquium on Automata, Languages and Processing, 2003. |
| [7] | R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent rounding in bipartite graphs. In Proceedings, IEEE Symposium on Foundations of Computer Science, pages 323-332, 2002. |
| [8] | D. Grable and A. Panconesi. Nearly optimal distributed edge colouring in o(log log n) rounds. Random Structures and Algorithms, 10(3):385-405, 1997. 10.1002/(SICI)1098-2418(199705)10:3 · Zbl 0876.05087 |
| [9] | S. Guha, R. Hassin, S. Khuller, and E. Or. Capacitated vertex covering with applications. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms, pages 858-865, 2002. · Zbl 1093.68620 |
| [10] | Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput., 31, 2002. 10.1137/S0097539700381097 · Zbl 1041.68130 |
| [11] | D. S. Hochbaum. Approximation algorithms for set covering and vertex cover problems. SIAM J. Comput., 11:555-556, 1982. · Zbl 0486.68067 |
| [12] | Jain and Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. JACM: Journal of the ACM, 48, 2001. 10.1145/375827.375845 · Zbl 1138.90417 |
| [13] | S. Khuller, U. Vishkin, and N. Young. A primal-dual prallel approximation technique applied to weighted set and vertex covers. J. Algorithms, 17(2):280-289, 1994. 10.1006/jagm.1994.1036 · Zbl 0938.68946 |
| [14] | F. Kuhn and R. Wattenhofer. Constant-time distributed dominating set approximation. In Proceedings, ACM Symposium on Principles of Distributed Computing, pages 25-32, 2003. 10.1145/872035.872040 · Zbl 1321.68479 |
| [15] | R. Rajaraman L. Jia and T. Suel. An efficient distributed algorithm for constructing small dominating sets. Proceedings, ACM Symposium on Principles of Distributed Computing, 2001. |
| [16] | M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15:1036-1053, 1986. 10.1137/0215074 · Zbl 0619.68058 |
| [17] | M. Luby. Removing randomness in parallel without processor penalty. J. Comput. System Sci., 47(2):250-286, 1993. 10.1016/0022-0000(93)90033-S · Zbl 0784.68035 |
| [18] | A. Panconesi and A. Srinivasan. The local nature of delta-coloring and its algorithmic applications. Combinatorica, 15(2):255-280, 1995. · Zbl 0837.68043 |
| [19] | Khaled M. Alzoubi Peng-Jun Wan and Ophir Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. Proceedings of Infocom, 2002. |
| [20] | S. Rajagopalan and V.V. Vazirani. Primal-dual rnc approximation algorithms for (multi)set (multi)cover and covering integer programs. SIAM J. Comput., 28(2):525-540, 1998. 10.1137/S0097539793260763 · Zbl 0914.68096 |
| [21] | R. Rajaraman. Topology control and routing in ad hoc networks: a survey. Sigact News, 2002. 10.1145/564585.564602 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
