2840 EEE TRANSACTIONS ON MOBILE COMPUTING,VOL 16.NO.10,OCTOBER 2017 variables.We want to solve them,and finally to revert to the PDA starts with a primal infeasible solution and a dual original integral problem. feasible solution.It iteratively improves the feasibility of the Let 0,=ISCA-MP-DL becomes primal solution and the optimality of the dual solution.It ensures that(i)the primal solution is always extended inte- max j ISCA-MP-DL-T] (13a) grally,and that (ii)the value of the dual solution is at least f 85S times as large as the value of the primal solution.Since the dual solution is a lower bound on the optimal value of the st.∑≤0 i r:∈R (13b) primal solution,the approximation ratio is then equal to f. 55 9citij Alg.PDA(Primal-Dual schema-Based Algorithm) 0-≤i+10 s∈S,rn∈R (13c Part II:Compute integral primal solution 21.i,i,x←-0：i,h-0,fselected-0 45≥0， ∀s,∈S (13d) 22.Ris-friltselectedi =1} ≥0， ∀s∈S,ri∈R (13e) 23.Construct a graph G with Ri as vertex set.For each pair of ri,riERs,there is an edge between them if and only if The integral dual of ISCA-MP-DL-T,i.e.,the transformed 3sj∈S,s.t.positive=positive为=1. ISCA-MP,is as follows: 24.Find a maximal independent vertex set in G with non-decreasing order of,say D. min iISCA-MP-T] 25.For each riE D,set yi -1,fselectedi-1. 10T 26.For each si do (14) 27. Ry-{rr:∈Rts,f>0} s.t. Egs.(5e),(5f),and (5h) 28.If,then RinD has only one element ri. 斯∈2+，r:eR 29. Setzij-1,sj is called closely covered. 30. Else if chosti ED,let rk-chosti Note that the constraint Eq.(5g)is discarded in Eq.(14); 31. Set kj -1,sj is called normally covered. therefore,in ISCA-MP-T,there is no constraint on the capac- 32. Otherwise,D must contain rh,such that ry and rh are ity of each itinerary. neighbors in G,and ch/Th ce/T 33. Setj-1,sj is called loosely covered. 5.4 Approximation Algorithm for ISCA-MP-T 34.xs and ys form an integral solution to ISCA-MP-T We now consider two problems:the primal problem,i.e., ISCA-MP-T,and the dual problem,i.e.,ISCA-MP-DL-T. PDA consists of two parts,which correspond to comput- There is a factor three approximation algorithm for the facil-ing dual and integral primal solutions,respectively.In the ity location problem in [33].Based on that algorithm and following,we first introduce these two parts and then pro- some special properties of ISCA-MP-T,we now propose a vide the analysis of the approximation ratio. factor nine approximation algorithm for ISCA-MP-T using the primal-dual schema,shown in Alg.PDA.The main intu- 5.4.1 Compute Dual Solution ition behind PDA is as follows. The objective of ISCA-MP-DL-T is to maximize The first part of PDA tries to increase asas much as possible Alg.PDA(Primal-Dual Schema-Based Algorithm) and maintains Eqs.(13b)and(13c). Part I:Compute dual solution All events are associated with a timestamp ts.When ts is 1.Vi,tselected;-0 zero,each itinerary is not temporarily selected(tselected); 2.j,&;←-0，covered;←-0，chost-0 each a is 0;each device is not covered(covered);the covering 3.ii,B-0,fullij←-0，positive6-0 host (chost)of each device is 0;each B is 0;the connection 4.Timestamp ts -0 between ri and sj is neither full nor positive. 5.While there is any uncovered device do PDA raises a by one for each uncovered device as ts 6. ts+ts+1 7.For each s;that satisfies covered;=0 do grows by one (line 8).For each ri that satisfies aj= +0,PDA runs as follows: 9c:t: 8. aj-aj+1 9. For eachrthat satisfiesdo the connection between itinerary ri and device sj 10. fullij-1 becomes full (line 10); 11. If tselected;1 and covered;=0 do if ri is temporarily selected and sj is not covered,we 12. covered←-1，chostj-r For eachthat satisfies>方+密do change sj into covered and its covering host is ri 13. ines11-12). 14. Bj-月+1，positiver-1 15. If∑，sA=年do And for each that satisfiesPDA runs as follows: 16. tselected←-l 17. For each se that satisfies covered:=0 .B;is increased by one and the corresponding con- and fullik =1 do nection is set to be positive (line 14),ensuring that 18. coveredk-1,chosts-ri Eq.(13 c)is not violated; 19.as and Bs form a dual solution to ISCA-MP-DL-T ·if∑s,esB=靠thenr,is marked as temporarily selected,all uncovered devices that have fullvariables. We want to solve them, and finally to revert to the original integral problem. Let ui ¼ 9ci 10Ti . ISCA-MP-DL becomes max X sj2S aj [ISCA-MP-DL-T] (13a) s.t.X sj2S bij ci 10 ; 8ri 2 R (13b) aj  bij fij þ 9citij 10Ti ; 8sj 2 S; ri 2 R (13c) aj  0; 8sj 2 S (13d) bij  0; 8sj 2 S; ri 2 R (13e) The integral dual of ISCA-MP-DL-T, i.e., the transformed ISCA-MP, is as follows: min X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij[ISCA-MP-T] s.t. Eqs. (5e), (5f), and (5h) yi 2 Zþ; 8ri 2 R (14) Note that the constraint Eq. (5g) is discarded in Eq. (14); therefore, in ISCA-MP-T, there is no constraint on the capac￾ity of each itinerary. 5.4 Approximation Algorithm for ISCA-MP-T We now consider two problems: the primal problem, i.e., ISCA-MP-T, and the dual problem, i.e., ISCA-MP-DL-T. There is a factor three approximation algorithm for the facil￾ity location problem in [33]. Based on that algorithm and some special properties of ISCA-MP-T, we now propose a factor nine approximation algorithm for ISCA-MP-T using the primal-dual schema, shown in Alg. PDA. The main intu￾ition behind PDA is as follows. Alg. PDA (Primal-Dual Schema-Based Algorithm) Part I: Compute dual solution 1. 8i, tselectedi 0 2. 8j, aj 0, coveredj 0, chostj 0 3. 8i; j, bij 0, fullij 0, positiveij 0 4. Timestamp ts 0 5. While there is any uncovered device do 6. ts ts þ 1 7. For each sj that satisfies coveredj ¼ 0 do 8. aj aj þ 1 9. For each ri that satisfies aj ¼ fij þ 9citij 10Ti do 10. fullij 1 11. If tselectedi ¼ 1 and coveredj ¼ 0 do 12. coveredj 1, chostj ri 13. For each ri that satisfies aj > fij þ 9citij 10Ti do 14. bij bij þ 1, positiveij 1 15. If P sj2S bij ¼ ci 10 do 16. tselectedi 1 17. For each sk that satisfies coveredk ¼ 0 and fullik ¼ 1 do 18. coveredk 1, chostk ri 19. as and bs form a dual solution to ISCA-MP-DL-T PDA starts with a primal infeasible solution and a dual feasible solution. It iteratively improves the feasibility of the primal solution and the optimality of the dual solution. It ensures that (i) the primal solution is always extended inte￾grally, and that (ii) the value of the dual solution is at least f times as large as the value of the primal solution. Since the dual solution is a lower bound on the optimal value of the primal solution, the approximation ratio is then equal to f. Alg. PDA (Primal-Dual schema-Based Algorithm) Part II: Compute integral primal solution 21. 8i; j, xij 0; 8i, yi 0, fselectedi 0 22. Rts frijtselectedi ¼ 1g 23. Construct a graph G with Rts as vertex set. For each pair of ri; rk 2 Rts, there is an edge between them if and only if 9sj 2 S, s.t. positiveij ¼ positivekj ¼ 1. 24. Find a maximal independent vertex set in G with non-decreasing order of ci Ti , say D. 25. For each ri 2 D, set yi 1, fselectedi 1. 26. For each sj do 27. Rj frijri 2 Rts; bij > 0g 28. If Rj \ D 6¼ ;, then Rj \ D has only one element ri. 29. Set xij 1, sj is called closely covered. 30. Else if chostj 2 D, let rk chostj 31. Set xkj 1, sj is called normally covered. 32. Otherwise, D must contain rh, such that rk and rh are neighbors in G, and ch=Th ck=Tk 33. Set xhj 1, sj is called loosely covered. 34. xs and ys form an integral solution to ISCA-MP-T PDA consists of two parts, which correspond to comput￾ing dual and integral primal solutions, respectively. In the following, we first introduce these two parts and then pro￾vide the analysis of the approximation ratio. 5.4.1 Compute Dual Solution The objective of ISCA-MP-DL-T is to maximize P sj2S aj. The first part of PDA tries to increase as as much as possible and maintains Eqs. (13b) and (13c). All events are associated with a timestamp ts. When ts is zero, each itinerary is not temporarily selected (tselected); each a is 0; each device is not covered (covered); the covering host (chost) of each device is 0; each b is 0; the connection between ri and sj is neither full nor positive. PDA raises a by one for each uncovered device as ts grows by one (line 8). For each ri that satisfies aj ¼ fij þ 9citij 10Ti , PDA runs as follows: the connection between itinerary ri and device sj becomes full (line 10); if ri is temporarily selected and sj is not covered, we change sj into covered and its covering host is ri (lines 11-12). And for each ri that satisfies aj > fij þ 9citij 10Ti , PDA runs as follows: bij is increased by one and the corresponding con￾nection is set to be positive (line 14), ensuring that Eq. (13 c) is not violated; if P sj2S bij ¼ ci 10, then ri is marked as temporarily selected, all uncovered devices that have full 2840 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017