2842 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL 16.NO.10,OCTOBER 2017 According to lines 24 and 32-33,we have ch/T c/Tk. To prove Eq.(18),it is sufficient to prove that /3 +器 2 4/3 10202040 1/2 6 9 12 4/3 -o+r-d+ 9Ecn(b+dhj) 10aPTh ,(Eqs.(3)and(4) 10 ≤b+dg+g+dsP-d 10 5 10 5 10 +9aE6+dg+g+d（rnt） 10aPTh (a)PDA inputs ≤盟o+4wP+b+dP+6+dgP-3a--2剑 6B66 686 +2TcnEl(b+dho)+(+da)+d) 10aPTi s3E[(0+dh)-a+(0+do)2-a+(+dj)2-a] ts=2 fs=4 l8=6 a full ---positive ◆tselected=1 △covered=1 27cnE(b+dng)27cnE(b+do 27cnE(+dx) (b)PDA in different timestamps 10aPT 10aPTh 10aPT Fig.5.Example of running PDA.Note that the a of a device will not ≤3(fng+fg+f)+3 (9cntng 9cht超 9cntki increase after being covered.The final solution is,s and s2 are closely 10Th covered by r and r1,respectively;ss and s are normally covered by r 10T6 10T and rs,respectively. ≤3(jg+fg+f)+3 (9chtng 9cktka 9cktkj 10Th 10T 10T Theorem 5.PDA plus Eq.(20)is a factor 10 approximation ≤3(ag+ag+a) algorithm for ISCA with multipick. ≤9ujr Proof..Notice that≤h+∑es where the third "<"is due to 8b2 2a,as a and b are T ,then we have know constants,and b is much bigger than a. Q ∑+∑∑ 防ER Combining the above analyses and Theorem 3,we have ri∈R8ES Theorem 4.PDA is a factor nine approximation algorithm for ∑+三 ISCA-MP-T. TiE riER BjES Proof.As previously mentioned,due to the weak duality ∑sr\ theorem, sjsaj is a lower bound of OPr. T +∑∑ 片∈R防S Eqs.(15),(16),(17),and (18),help us build a upper bound of∑，eR0+∑，eR∑ses+zy in terms of ∑jes4jnie ++器) ∑+∑∑（场+配） 09∑a S 10 ≤10∑a ≤9∑驰+∑∑+) 9citij 10 (19) ≤10.OPT ≤9∑g the theorem follows immediately. ◇ sjES Hereto,we have a constant-factor approximation for ISCA- ≤9.OPT MP,i.e.,charging with fixed itineraries in a general setting. Let L maxij(ci/10+fij+9citij/(10Ti)).In the first part the theorem follows immediately. of PDA,the maximal timestamp is at most L;in each itera- 5.5 Retransformation:Revert to ISCA-MP tion,PDA scans every connection between itineraries and uncovered devices.In the second part,constructing G In the previous sections,we have developed an approxima- requires O(MN)time;finding a maximal independent ver- tion algorithm of factor 9 for ISCA-MP-T.We now show tex set needs O(N2 log N)time.Therefore,the worst-case how to modify the results obtained by PDA for ISCA-MP. time complexity of PDA is O(LMN N2 log N). We denote by r's and ys the solution to ISCA-MP,and by rs and ys the solution generated by PDA for ISCA-MP-T. 5.6 Example of Running PDA In order to respect constraint(5g),we let We use an example to better illustrate the details of PDA. Fig.5a shows the inputs (i.e.,cis,Tis,tus,and fijs)of the =x,and (20) algorithm.There are 4 itineraries and 4 devices to cover. Fig.5b shows how PDA works in different timestamps.According to lines 24 and 32-33, we have ch=Th ck=Tk. To prove Eq. (18), it is sufficient to prove that fhj þ 9chthj 10Th ¼ E a ðb þ dhjÞ 2  a h i þ 9Echðb þ dhjÞ 2 10aPTh ðEqs. (3) and (4)Þ E a ðb þ dhg þ dkg þ dkjÞ 2  a h i þ 9chEðb þ dhg þ dkg þ dkjÞ 2 10aPTh ðtriangle inequalityÞ 3E a ðb þ dhgÞ 2 þ ðb þ dkgÞ 2 þ ðb þ dkjÞ 2  3a  ð8b2  2aÞ h i þ 27chE½ðb þ dhgÞ 2 þ ðb þ dkgÞ 2 þ ðb þ dkjÞ 2  10aPTh 3E a ðb þ dhgÞ 2  a þ ðb þ dkgÞ 2  a þ ðb þ dkjÞ 2  a h i þ 27chEðb þ dhgÞ 2 10aPTh þ 27chEðb þ dkgÞ 2 10aPTh þ 27chEðb þ dkjÞ 2 10aPTh " # 3ðfhg þ fkg þ fkjÞ þ 3 9chthg 10Th þ 9chtkg 10Th þ 9chtkj 10Th  3ðfhg þ fkg þ fkjÞ þ 3 9chthg 10Th þ 9cktkg 10Tk þ 9cktkj 10Tk  3ðag þ ag þ ajÞ 9aj; where the third “” is due to 8b2  2a, as a and b are know constants, and b is much bigger than a. tu Combining the above analyses and Theorem 3, we have Theorem 4. PDA is a factor nine approximation algorithm for ISCA-MP-T. Proof. As previously mentioned, due to the weak duality theorem, P sj2S aj is a lower bound of OPT. Eqs. (15), (16), (17), and (18), help us build a upper bound of P ri2R ciyi 10 þ P ri2R P sj2Sðfij þ 9citij 10Ti Þxij P in terms of sj2S aj, i.e., X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij 9 X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij 9 X sj2S aj 9  OPT; (19) the theorem follows immediately. tu 5.5 Retransformation: Revert to ISCA-MP In the previous sections, we have developed an approxima￾tion algorithm of factor 9 for ISCA-MP-T. We now show how to modify the results obtained by PDA for ISCA-MP. We denote by x0 s and y0 s the solution to ISCA-MP, and by xs and ys the solution generated by PDA for ISCA-MP-T. In order to respect constraint (5g), we let x0 ij ¼ xij; and y0 i ¼ P sj2S tijxij Ti & ’: (20) Theorem 5. PDA plus Eq. (20) is a factor 10 approximation algorithm for ISCA with multipick. Proof. Notice that y0 i yi þ P sj2S tijxij Ti , then we have X ri2R ciy0 i þ X ri2R X sj2S fijx0 ij X ri2R ciy0 i þ 10 9 X ri2R X sj2S fijx0 ij 10 9  9 10 X ri2R ci yi þ P sj2S tijxij Ti  þ X ri2R X sj2S fijx0 ij ¼ 10 9  9 X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti  xij 10 9 9 X sj2S aj 10X sj2S aj 10  OPT; the theorem follows immediately. tu Hereto, we have a constant-factor approximation for ISCA￾MP, i.e., charging with fixed itineraries in a general setting. Let L ¼ maxi;jðci=10 þ fij þ 9citij=ð10TiÞÞ. In the first part of PDA, the maximal timestamp is at most L; in each itera￾tion, PDA scans every connection between itineraries and uncovered devices. In the second part, constructing G requires OðMNÞ time; finding a maximal independent ver￾tex set needs OðN2 log NÞ time. Therefore, the worst-case time complexity of PDA is OðLMN þ N2 log NÞ. 5.6 Example of Running PDA We use an example to better illustrate the details of PDA. Fig. 5a shows the inputs (i.e., cis, Tis, tijs, and fijs) of the algorithm. There are 4 itineraries and 4 devices to cover. Fig. 5b shows how PDA works in different timestamps. Fig. 5. Example of running PDA. Note that the a of a device will not increase after being covered. The final solution is, s1 and s2 are closely covered by r3 and r1, respectively; s3 and s4 are normally covered by r1 and r3, respectively. 2842 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017