TY - GEN
T1 - Revisiting connected dominating sets
T2 - 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
AU - Khuller, Samir
AU - Yang, Sheng
N1 - Funding Information:
This work is supported by NSF grant CCF 1217890.
PY - 2016/9/1
Y1 - 2016/9/1
N2 - In this paper we consider the classical Connected Dominating Set (CDS) problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem-a centralized greedy approach with an approximation guarantee of H(δ)+2, and a local greedy approach with an approximation guarantee of 2(H(δ) + 1) (where H() is the harmonic function, and δ is the maximum degree in the graph). A local greedy algorithm uses significantly less information about the graph, and can be useful in a variety of contexts. However, a fundamental question remained-can we get a local greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of "2" in the approximation factor? In this paper, we answer that question in the affirmative.
AB - In this paper we consider the classical Connected Dominating Set (CDS) problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem-a centralized greedy approach with an approximation guarantee of H(δ)+2, and a local greedy approach with an approximation guarantee of 2(H(δ) + 1) (where H() is the harmonic function, and δ is the maximum degree in the graph). A local greedy algorithm uses significantly less information about the graph, and can be useful in a variety of contexts. However, a fundamental question remained-can we get a local greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of "2" in the approximation factor? In this paper, we answer that question in the affirmative.
KW - Approximation Algorithms
KW - Dominating Sets
KW - Graph Algorithms
KW - Local Information Algorithms
UR - http://www.scopus.com/inward/record.url?scp=84990855862&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84990855862&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2016.11
DO - 10.4230/LIPIcs.APPROX-RANDOM.2016.11
M3 - Conference contribution
AN - SCOPUS:84990855862
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
A2 - Jansen, Klaus
A2 - Mathieu, Claire
A2 - Rolim, Jose D. P.
A2 - Umans, Chris
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 7 September 2016 through 9 September 2016
ER -