Article

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities

Authors:

M. SozioAuthors Info & Claims

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

Pages 118 - 125

https://doi.org/10.1145/1073814.1073835

Published: 17 July 2005 Publication History

Abstract

In this paper we consider the weighted, capacitated vertex cover problem with hard capacities (capVC). Here, we are given an undirected graph G=(V,E), non-negative vertex weights wt_v for all vertices v ∈ V, and node-capacities B_v ≥ 1 for all v ∈ V. A feasible solution to a given capVC instance consists of a vertex cover C ⊆ V. Each edge e ∈ E is assigned to one of its endpoints in C and the number of edges assigned to any vertex v ∈ C is at most B_v. The goal is to minimize the total weight of C.For a parameter ε>0 we give a deterministic, distributed algorithm for the capVC problem that computes a vertex cover C of weight at most (2+ε) • opt where opt is the weight of a minimum-weight feasible solution to the given instance. The number of edges assigned to any node v ∈ C is at most (4+ε)• B_v. The running time of our algorithm is O(log (n W)/ε), where n is the number of nodes in the network and W=wt_max/weight_min is the ratio of largest to smallest weight.This result is complemented by a lower-bound saying that any distributed algorithm for capVC which requires a poly-logarithmic number of rounds is bound to violate the capacity constraints by a factor two.The main feature of the algorithm is that it is derived in a systematic fashion starting from a primal-dual sequential algorithm.

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.

[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.

Digital Library

[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.

Digital Library

[5]

U. Feige. A threshold of ln n for approximating set cover. In Proceedings, ACM Symposium on Theory of Computing, pages 314--318, 1996.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[10]

Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput., 31, 2002.

Digital Library

[11]

D. S. Hochbaum. Approximation algorithms for set covering and vertex cover problems. SIAM J. Comput., 11:555--556, 1982.

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[17]

M. Luby. Removing randomness in parallel without processor penalty. J. Comput. System Sci., 47(2):250--286, 1993.

Digital Library

[18]

A. Panconesi and A. Srinivasan. The local nature of delta-coloring and its algorithmic applications. Combinatorica, 15(2):255--280, 1995.

[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.

Digital Library

[21]

R. Rajaraman. Topology control and routing in ad hoc networks: a survey. Sigact News, 2002.

Digital Library

Cited By

Lim HYong INg P(2019)Imperative Selection Intensity of Parent Selection Operator in Evolutionary Algorithm Hybridization for Nurse Scheduling ProblemEmerging Trends in Intelligent Computing and Informatics10.1007/978-3-030-33582-3_23(235-244)Online publication date: 2-Nov-2019
https://doi.org/10.1007/978-3-030-33582-3_23
Albath JThakur MMadria S(2013)Energy constraint clustering algorithms for wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2013.05.01611:8(2512-2525)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.adhoc.2013.05.016
Khan MKuhn FMalkhi DPandurangan GTalwar K(2012)Efficient distributed approximation algorithms via probabilistic tree embeddingsDistributed Computing10.1007/s00446-012-0157-925:3(189-205)Online publication date: 28-Jan-2012
https://doi.org/10.1007/s00446-012-0157-9
Show More Cited By

Index Terms

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R ⁺, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the ...
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover

In this paper we consider the capacitated vertex cover problem, which is the variant of vertex cover where each node is allowed to cover a limited number of edges. We present an efficient, deterministic, distributed approximation algorithm for the ...
Distributed weighted vertex cover via maximal matchings

In this article, we consider the problem of computing a minimum-weight vertex-cover in an n-node, weighted, undirected graph G = (V,E). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

July 2005

364 pages

ISBN:1581139942

DOI:10.1145/1073814

General Chair:
Marcos Aguilera
HP Labs
,
Program Chair:
James Aspnes
Yale University

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC05

Sponsor:

PODC05: ACM Symposium on Principles of Distributed Computing

July 17 - 20, 2005

NV, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
405
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lim HYong INg P(2019)Imperative Selection Intensity of Parent Selection Operator in Evolutionary Algorithm Hybridization for Nurse Scheduling ProblemEmerging Trends in Intelligent Computing and Informatics10.1007/978-3-030-33582-3_23(235-244)Online publication date: 2-Nov-2019
https://doi.org/10.1007/978-3-030-33582-3_23
Albath JThakur MMadria S(2013)Energy constraint clustering algorithms for wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2013.05.01611:8(2512-2525)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.adhoc.2013.05.016
Khan MKuhn FMalkhi DPandurangan GTalwar K(2012)Efficient distributed approximation algorithms via probabilistic tree embeddingsDistributed Computing10.1007/s00446-012-0157-925:3(189-205)Online publication date: 28-Jan-2012
https://doi.org/10.1007/s00446-012-0157-9
Koufogiannakis CYoung N(2011)Distributed algorithms for covering, packing and maximum weighted matchingDistributed Computing10.1007/s00446-011-0127-724:1(45-63)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1007/s00446-011-0127-7
Sultanik EShokoufandeh ARegli WLuck MSen S(2010)Dominating sets of agents in visibility graphsProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 110.5555/1838206.1838312(797-804)Online publication date: 10-May-2010
https://dl.acm.org/doi/10.5555/1838206.1838312
Albath JThakur MMadria S(2010)Energy Constrained Dominating Set for Clustering in Wireless Sensor NetworksProceedings of the 2010 24th IEEE International Conference on Advanced Information Networking and Applications10.1109/AINA.2010.14(812-819)Online publication date: 20-Apr-2010
https://dl.acm.org/doi/10.1109/AINA.2010.14
Kuhn FMoscibroda T(2010)Distributed Approximation of Capacitated Dominating SetsTheory of Computing Systems10.1007/s00224-010-9271-x47:4(811-836)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1007/s00224-010-9271-x
Koufogiannakis CYoung NTirthapura SAlvisi L(2009)Distributed and parallel algorithms for weighted vertex cover and other covering problemsProceedings of the 28th ACM symposium on Principles of distributed computing10.1145/1582716.1582746(171-179)Online publication date: 10-Aug-2009
https://dl.acm.org/doi/10.1145/1582716.1582746
Khan MKuhn FMalkhi DPandurangan GTalwar KBazzi RPatt-Shamir B(2008)Efficient distributed approximation algorithms via probabilistic tree embeddingsProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400787(263-272)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.1145/1400751.1400787
Santos MDrummond LUchoa E(2007)A distributed primal-dual heuristic for steiner problems in networksProceedings of the 6th international conference on Experimental algorithms10.5555/1768570.1768589(175-188)Online publication date: 6-Jun-2007
https://dl.acm.org/doi/10.5555/1768570.1768589
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents