large group.Here V denotes the set of users and APs,and According to Lemma 1, E denotes links after weak link eliminations.If the graph is disconnected somewhere due to the effect of weak link ∑WP≤∑∑Wnd=∑W elimination,we will obtain new sub-groups. jEGiES jEG iES B.Approximation Ratio Analysis Then Assume that for any user j in the original optimized solution without edge removal,we have bandwidth b;for the fractional ∑W动≤∑W6+∑Wrp jEG iEG jEGiEA-S solution and b;for the integral solution;and similarly in the approximate solution with edge removal,we have bandwidth Thus by the definition of weak link (i,j)with i Aj-Sj. b,for the fractional solution and b for the integral solution. we have ri.j<月j·Rj,where R=maxicA,ri,j·Then For both the efficiency and fairness metrics,we define the Liec Wy.by approximation ratio as Apparently the ratio is at ∑wb≤∑W6+∑(3RwW,·∑p jEG jEG jEG iEAj-Sy least 1 as∑iecW:6;≥∑jecW:g,since the candidate link set for the original solution is a superset of the one for Since∑ieA,-S,P,i≤1，then approximate solution.In the following we give an upper bound for this approximation ratio. ∑Wb≤∑W4+∑WR For any user j.we denote Aj as its original candidate AP jEG jEG jEG set,and S,as a subset of A;for the remaining candidate AP set after the weak link elimination.Thus A;-Sj is the As we have ∑jecW;·b≤∑jecW·bj because the set of those eliminated candidate APs.We respectively utilize fractional optimal solution can always achieve a better result matrix Pi.j and p to denote the optimized parameters for the than the integral optimal solution,then original solution and the approximate solution.Then according EoWE<EaWb<∑EaWb+ΣEewB to the definition we have ∑jecW-b ∑jecW6 ∑ecWb b=∑ipj=∑rp+∑ Ti.jpi.j iEA iES iEA-S We set 0= to be the approximation ratio for the (20) ∑1EGWb rounding algorithms proposed by Shmoy and Tardos[16],and =∑r,=∑r (21)1≤0≤2.So. iEA iES, We have the property in Lemma 1. ∑jecW· s0+eo西÷R Lemma 1:For optimal parameters pi.j in set Si for the ∑jecW,· ∑jecW· original solution and optimal parameters p;in set Sj for the approximate solution,W After the weak link elimination,the optimal integral solution may come with a worst case,where a bunch of users share only ∑jeg∑es,Wr: Proof:After removing some weak links,those pij with one candidate AP which has the largest bit rate for any of them, iSj corresponding to the weak links are set to 0. with the other candidate APs all eliminated.Then the optimal method for each user j is to select the unique AP with Ri Consequently some constraints for the remaining pi.j with iE Sj get relaxed.We can then add a slack value to adjust which is the largest for j.Thus we have jWj pij to pj so as to further increase the objective function as the lower bound for the optimal result jW.So. sW which at least can remain the same by setting p=pij.Therefore the objective function of the ∑ieGW·6 s0+ ∑ecW·÷·B optimal solution should be equal to or larger than the previous ∑jecW· ∑，ecW品 <0+1 one,ie.∑jec∑ies,Wrpi≤∑jec∑ies,Wri,P The lemma gets proved. ■ Therefore we obtain the approximation ratio as +y, Theorem 6:For the snapshot solution of the weight based where yy is a constant.This indicates we can well control the objective function,the upper bound of the approximation ratio approximation ratio by adjusting y. ■ for group breaking is 0+,where is the approximation ratio for the rounding algorithm in Shmoy and Tardos[16]. C.Computation Complexity Proof:According to Eq.(20)and Eq.(21), Note that the number of variables for the original linear ∑Wb=∑∑Wr+∑∑Wp program is N m.n.After the weak link elimination,we jEG jEGiES j∈GiEA-S can break a large group of APs and users into sub-groups G1,G2,...,Gk.For each group Gi (1 <i<k),we have mi ∑W6=∑∑Wp APs and ni users.Thus,the number of variables for the linear jEGiES program is NmSuppose the expected number 331 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply.large group. Here V denotes the set of users and APs, and E denotes links after weak link eliminations. If the graph is disconnected somewhere due to the effect of weak link elimination, we will obtain new sub-groups. B. Approximation Ratio Analysis Assume that for any user j in the original optimized solution without edge removal, we have bandwidth bj for the fractional solution and ˆbj for the integral solution; and similarly in the approximate solution with edge removal, we have bandwidth b j for the fractional solution and ˆb j for the integral solution. For both the efficiency and fairness metrics, we define the approximation ratio as j∈G Wj ·b ˆ j j∈G Wj · ˆb j . Apparently the ratio is at least 1 as j∈G Wj · ˆbj ≥ j∈G Wj · ˆb j, since the candidate link set for the original solution is a superset of the one for approximate solution. In the following we give an upper bound for this approximation ratio. For any user j, we denote Aj as its original candidate AP set, and Sj as a subset of Aj for the remaining candidate AP set after the weak link elimination. Thus Aj − Sj is the set of those eliminated candidate APs. We respectively utilize matrix pi,j and p i,j to denote the optimized parameters for the original solution and the approximate solution. Then according to the definition we have bj =  i∈Aj ri,j · pi,j =  i∈Sj ri,j · pi,j +  i∈Aj−Sj ri,j · pi,j (20) b j =  i∈Aj ri,j · p i,j =  i∈Sj ri,j · p i,j . (21) We have the property in Lemma 1. Lemma 1: For optimal parameters pi,j in set Sj for the original solution and optimal parameters p i,j in set Sj for the approximate solution, j∈G i∈Sj Wj ri,jpi,j ≤ j∈G i∈Sj Wj ri,jp i,j . Proof: After removing some weak links, those pi ,j with i ∈/ Sj corresponding to the weak links are set to 0. Consequently some constraints for the remaining pi,j with i ∈ Sj get relaxed. We can then add a slack value to adjust pi,j to p i,j so as to further increase the objective function j∈G i∈Sj Wj ri,jpi,j , which at least can remain the same by setting p i,j = pi,j. Therefore the objective function of the optimal solution should be equal to or larger than the previous one, i.e. j∈G i∈Sj Wj ri,jpi,j ≤ j∈G i∈Sj Wj ri,jp i,j . The lemma gets proved. Theorem 6: For the snapshot solution of the weight based objective function, the upper bound of the approximation ratio for group breaking is θ+γ, where θ is the approximation ratio for the rounding algorithm in Shmoy and Tardos[16]. Proof: According to Eq. (20) and Eq. (21),  j∈G Wj bj =  j∈G  i∈Sj Wj ri,j · pi,j +  j∈G  i∈Aj−Sj Wj ri,j · pi,j .  j∈G Wj b j =  j∈G  i∈Sj Wj ri,j · p i,j . According to Lemma 1,  j∈G  i∈Sj Wj ri,jpi,j ≤  j∈G  i∈Sj Wj ri,jp i,j =  j∈G Wj b j. Then  j∈G Wj bj ≤  j∈G Wj b j +  j∈G  i∈Aj−Sj Wj ri,j · pi,j . Thus by the definition of weak link (i, j) with i ∈ Aj − Sj , we have ri,j < βj · Rj , where Rj = maxi∈Aj ri,j . Then  j∈G Wj bj ≤  j∈G Wj b j +  j∈G (βjRjWj ·  i∈Aj−Sj pi,j ). Since i∈Aj−Sj pi,j ≤ 1, then  j∈G Wj bj ≤  j∈G Wj b j +  j∈G WjβjRj . As we have j∈G Wj · b j ≤ j∈G Wj · bj because the fractional optimal solution can always achieve a better result than the integral optimal solution, then j∈G Wj ·b j j∈G Wj · b j ≤ j∈G Wj ·bj j∈G Wj · b j ≤ j∈G Wj ·b j+ j∈G Wj ·βj·Rj j∈G Wj · b j . We set θ = j∈G Wj ·b j j∈G Wj · b j to be the approximation ratio for the rounding algorithms proposed by Shmoy and Tardos[16], and 1 ≤ θ ≤ 2. So, j∈G Wj · b j j∈G Wj · b j ≤ θ + j∈G Wj · γ ci∗ · Rj j∈G Wj · b j . After the weak link elimination, the optimal integral solution may come with a worst case, where a bunch of users share only one candidate AP which has the largest bit rate for any of them, with the other candidate APs all eliminated. Then the optimal method for each user j is to select the unique AP with Rj , which is the largest ri,j for j. Thus we have j∈G Wj · Rj ci∗ as the lower bound for the optimal result j∈G Wj · b j . So, j∈G Wj · b j j∈G Wj · b j ≤ θ + j∈G Wj · γ ci∗ · Rj j∈G Wj · Rj ci∗ ≤ θ + γ Therefore we obtain the approximation ratio as θ + γ, where γ is a constant. This indicates we can well control the approximation ratio by adjusting γ. C. Computation Complexity Note that the number of variables for the original linear program is N = m · n. After the weak link elimination, we can break a large group of APs and users into sub-groups G1, G2, ..., Gk. For each group Gi (1 ≤ i ≤ k), we have mi APs and ni users. Thus, the number of variables for the linear program is N = k i=1 mi · ni. Suppose the expected number 331 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.