TY - GEN
T1 - Analyzing the optimal neighborhood
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
AU - Khuller, Samir
AU - Purohit, Manish
AU - Sarpatwar, Kanthi K.
PY - 2014
Y1 - 2014
N2 - We study partial and budgeted versions of the well studied connected dominating set problem. In the partial connected dominating set problem (PCDS), we are given an undirected graph G = (V,E) and an integer n', and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least n' vertices. We obtain the first polynomial time algorithm with an O(ln δ) approximation factor for this problem, thereby significantly extending the results of Guha and Khuller (Algorithmica, Vol. 20(4), Pages 374-387, 1998) for the connected dominating set problem. We note that none of the methods developed earlier can be applied directly to solve this problem. In the budgeted connected dominating set problem (BCDS), there is a budget on the number of vertices we can select, and the goal is to dominate as many vertices as possible. We obtain a -1/13(1 - 1/e) approximation algorithm for this problem. Finally, we show that our techniques extend to a more general setting where the profit function associated with a subset of vertices is a "special" submodular function. This general-ization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies a O(lnq) approximation (where q denotes the quota) and an O( 1) approximation algorithms for the partial and budgeted versions of these problems. While the algorithms are simple, the results make a surprising use of the greedy set cover framework in defining a useful profit function.
AB - We study partial and budgeted versions of the well studied connected dominating set problem. In the partial connected dominating set problem (PCDS), we are given an undirected graph G = (V,E) and an integer n', and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least n' vertices. We obtain the first polynomial time algorithm with an O(ln δ) approximation factor for this problem, thereby significantly extending the results of Guha and Khuller (Algorithmica, Vol. 20(4), Pages 374-387, 1998) for the connected dominating set problem. We note that none of the methods developed earlier can be applied directly to solve this problem. In the budgeted connected dominating set problem (BCDS), there is a budget on the number of vertices we can select, and the goal is to dominate as many vertices as possible. We obtain a -1/13(1 - 1/e) approximation algorithm for this problem. Finally, we show that our techniques extend to a more general setting where the profit function associated with a subset of vertices is a "special" submodular function. This general-ization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies a O(lnq) approximation (where q denotes the quota) and an O( 1) approximation algorithms for the partial and budgeted versions of these problems. While the algorithms are simple, the results make a surprising use of the greedy set cover framework in defining a useful profit function.
UR - http://www.scopus.com/inward/record.url?scp=84902095958&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902095958&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973402.123
DO - 10.1137/1.9781611973402.123
M3 - Conference contribution
AN - SCOPUS:84902095958
SN - 9781611973389
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1702
EP - 1713
BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PB - Association for Computing Machinery
Y2 - 5 January 2014 through 7 January 2014
ER -