constraint. We note that the Algorithm II can build a set using an optional greedy stage. This set is further refined in the enhanced local search stage comprising of addition, deletion and swap operations. At the termination of the LS stage we obtain the primary choice ˘ G . Then, both stages are repeated over the complement set, Ω \ ˘ G to generate an alternate choice, ˜ G . Finally, the choice yielding the larger weighted sum rate utility among the primary and alternate choices is chosen. Regarding the slight variation alluded to above, we note that the direct adaptation would have initialized the Enhanced LS stage with the empty set or the singleton set yielding the highest weighted rate, since the LS stage also includes adding (or insertion) of elements. However, in our numerical simulations we saw that initializing the LS stage using the output of the greedy stage helps in reducing the run-time without performance degradation. We proceed to derive performance guarantee for Algorithm II. Towards that end, we introduce an assumption pertaining to the feasibility of the minimum rates. We emphasize that this assumption is only for deriving a performance guarantee and is not needed for implementing the algorithm. Theorem 3. Algorithm II yields a constant factor ( 1 4+ $_{ϵ}$) approximation to (1) over all input instances for which the admission control assumption holds. Proof. Let ˜ I denote the family of sets obtained by taking the pairwise union of members of I . We define an extended set function as ˜ f $^{wsr}$( G ) = ∑ m ∈M ˜ f wsr m ( G ∩ Ω ( m $^{)}$) , ∀ G ∈ ˜ I . Here, for any G ∈ ˜ I we define ˜ f wsr m ( G ∩ Ω ( m $^{)}$) = ˆ O (1 , 1 ) , where ˆ O (1 , 1 ) is computed as described in Section III-A for the macro TP m and its set of pico TPs B$_{m}$ using unit budgets and the given association in G ∩ Ω ( m $^{)}$, with the following caveat. In particular, now in obtaining the user sets {U ( b $^{)}$} we treat the user in each tuple ( u, b ) ∈ G ∩ Ω ( m ) as a distinct virtual user. Hence, if ( u, b$_{1}$ ) and ( u, b$_{2}$ ) belong to G ∩ Ω ( m $^{)}$, we suppose that two distinct virtual users with their own separate peak rates and associated maximum and minimum rate limits are specified. These peak rates and limits are • Admission control assumption: Each macro TP m ∈ M can itself simultaneously meet twice the minimum rates of all users u that are present in at-least one tuple ( u, b ) ∈ Ω for any b ∈ B$_{m}$ . We now offer the following result which holds even when the greedy stage is skipped and which assumes that Algorithm II is initialized with MaxIter = ∞ and Δ = ϵ $_{C}$, where ϵ > 0 and C is a large enough constant that depends (polynomially) on the size of Ω .