Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems

摘要: We study partial and budgeted versions of the well studied connected dominating set problem. In problem, we are given an undirected graph G = (V,E) integer n', goal is to find a minimum subset vertices that induces subgraph dominates at least n' vertices. obtain first polynomial time algorithm with O(\ln \Delta) approximation factor for this thereby significantly extending results Guha Khuller (Algorithmica, Vol. 20(4), Pages 374-387, 1998) note none methods developed earlier can be applied directly solve there budget on number select, dominate as many possible. (1/13)(1 - 1/e) Finally, show our techniques extend more general setting where profit function associated monotone "special" submodular function. This generalization captures problem capacities and/or weighted profits special cases. implies q) (where q denotes quota) O(1) algorithms these problems. While simple, make surprising use greedy cover framework in defining useful