Algorithm 2 Approx.Alg.for P3 with Known Power Levels Algorithm 3 Two-Choice-based Approx.Alg.for P3 (TCA) Input:C,S,B,and H Input:C,S,and B Output:C' Output:C'and H 1:C1←-0，C2←-0 1:Z←-CxH 2:while B≥∑p;+minp:do 2:Z1←0，H1←-0 CrECI CIEC\CI c←arg max (Q(CI U Ic])-2(C1)) 3:while B≥min p(he)+∑_p(h)do EC\C,2Capm≤B (cih)EZ\Z (chE乙1 C1←-C1U{c} 4: 4 (C,）←arg (che-Ze2 P(h) max 5:end while (ZIU((c,h)))-Q(Zi) 6:while B≥Σpi+minp:do 5: Z1←-乙1U{(c,h)} CIEC2 GEC\C, 6: ifH[c]<h then Hi[c←-h cx←-arg max Q(CUlc)-Q(C2) C,eC\C2-Ecreczute PrSB Px 7:end while C2←C2U{cx 8:(C.H)-RemoveDuplicationAndUtilize(C,S,B,H1) 9:end while 9:Z2←0，H2←-0 10:return arg max (C) 1o:while B≥，min p(hg)+Σp(hg)do C∈C1C2 (cih)EZ\Z2 (ci.hse乙2 11: (c,h)←-arg max (c.h)EZ\Z2.Ehrzzuteh p(h)<B Q(Z2Ul(c.h))-Q(Z2) Equ.(5),the charger cw would be picked.However,if we pick 12: Z2←罗Uc,1 ci,c2,...and cN-1,the charging quality would be L.p(ci.s1) 13: ifH2[c]<h thenH[c←h instead of p(c1,s1)+e.When e is approaching zero,using 14:end while Equ.(5)would generate approximately 1/L of the charging quality returned by the optimal solution. 15:(C2.H2)--RemoveDuplicationAndUtilize(C,S,B,H2) 16:return arg max Another intuitive method is that,in each iteration,we pick (C.H)E((C:.H).(C.H2)) (C',H) the location that maximize the marginal ratio of objective gain 17: to power cost,i.e., 18:Sub-procedure:RemoveDuplicationAndUtilize 19:Input:C,S,B,and H Q(C'U lcx))-2(C) cx←arg .c (6) 20:Output:C'and H Px 21:C←-0，B←-0 However,we show in Fig.4(b)that,this method may also 22:for all H[ci]>0 do perform badly.In Fig.4(b),there are 2 candidate locations and 23: C'←CU{ch,B←-B+pHcl) M=L+1 devices;h 1,and h2 L;p(c1.s1)=p(c2.S2)= 24:end for p(c2,53)...p(c2,SM-1)=p(c2,SM)+E,where E satisfies 25:while B-B≥Pmin do 0<e<p(c1,s1).Given a power budget B=L.Pmin,using 26 G←argC{c,H+)-QC',田 Equ.(6).the charger cI would be picked.However,if we pick 27: C←CU{cl,Hcl←-H[cl+l,B←B+Pmim c2,the charging quality would be (L-1).p(c1,s1)+p(c2,SM) 28:end while instead of p(c1,s1).When e is approaching zero,this method 29:return (C,H) would also generate approximately 1/L of the charging quality returned by the optimal solution. Surprisingly enough,if we simultaneously apply the above chargers are 1,2....and L.We use (cih)to denote the two methods to the non-uniform case of p3 with fixed power charger of a constant power level h that can only be placed levels,and return the better one of the two results,we will at ci.Note that there are,in total,N.Lchargers.Given a power get an approx.algorithm (Alg.2)of factor(1-1)according budget B,how do we find a charger placement that maximize to [23].The time complexity of Alg.2 is also O(MN3). the objective function defined below? Let Z be the Cartesian product of C and H;denote by C.Approximation Algorithm for P3 Z'a subset of Z.We redefine several functions for the VP3 We design a probably good approximation algorithm,name- problem via overloading.The power p(ci,sj,h)received by ly TCA,in Alg.3 that simultaneously determines C'and H. device si from ci(its power level is hg)is Denote the set (1,2,...,L)by H;denote by Ii a row vector where the i-th element is 1 and all of the other elements are p(ci,Sj.hk)= p(hg) dc,s）≤Dhk, zeros,i.e.,I;=(0,0.....1....0).We use H[ci]to represent the 10 (7) dc,si）>Dhk. power level of a candidate location ci. Before giving some explanations about TCA,we first con- Correspondingly,given a charger placement Z,the to- sider the following variant of the P3 problem (VP3):For each tal power pz(sj)received by device sj is pz(sj)= candidate location ci.we are given L chargers with constant X(ehez p(ci.sj.hk).The charging quality of Z'on sj is but exactly different power levels,i.e.,the power levels of these Qz(s）=min(pz(sj,Ph (8)Algorithm 2 Approx. Alg. for P3 with Known Power Levels Input: C, S, B, and H Output: C ′ 1: C1 ← ∅, C2 ← ∅ 2: while B ≥ ∑ ci∈C1 pi + min ci∈C\C1 pi do 3: c ← arg max c∈C\C1, ∑ ci ∈C1∪{c} pi≤B (Q(C1 ∪ {c}) − Q(C1)) 4: C1 ← C1 ∪ {c} 5: end while 6: while B ≥ ∑ ci∈C2 pi + min ci∈C\C2 pi do 7: cx ← arg max cx∈C\C2, ∑ ci ∈C2∪{cx} pi≤B Q(C2∪{cx})−Q(C2) px 8: C2 ← C2 ∪ {cx} 9: end while 10: return arg max C′∈{C1,C2} Q(C ′ ) Equ. (5), the charger cN would be picked. However, if we pick c1, c2, ..., and cN−1, the charging quality would be L · p(c1, s1) instead of p(c1, s1) + ϵ. When ϵ is approaching zero, using Equ. (5) would generate approximately 1/L of the charging quality returned by the optimal solution. Another intuitive method is that, in each iteration, we pick the location that maximize the marginal ratio of objective gain to power cost, i.e., cx ← arg max cx∈C\C′ , ∑ ci ∈C′∪{cx} pi≤B Q(C ′ ∪ {cx}) − Q(C ′ ) px . (6) However, we show in Fig. 4(b) that, this method may also perform badly. In Fig. 4(b), there are 2 candidate locations and M = L + 1 devices; h1 = 1, and h2 = L; p(c1, s1) = p(c2, s2) = p(c2, s3)... = p(c2, sM−1) = p(c2, sM) + ϵ, where ϵ satisfies 0 < ϵ < p(c1, s1). Given a power budget B = L · pmin, using Equ. (6), the charger c1 would be picked. However, if we pick c2, the charging quality would be (L − 1) · p(c1, s1) + p(c2, sM) instead of p(c1, s1). When ϵ is approaching zero, this method would also generate approximately 1/L of the charging quality returned by the optimal solution. Surprisingly enough, if we simultaneously apply the above two methods to the non-uniform case of P3 with fixed power levels, and return the better one of the two results, we will get an approx. algorithm (Alg. 2) of factor 1 2 (1− 1 e ) according to [23]. The time complexity of Alg. 2 is also O(MN3 ). C. Approximation Algorithm for P3 We design a probably good approximation algorithm, name￾ly TCA, in Alg. 3 that simultaneously determines C ′ and H. Denote the set {1, 2, ..., L} by H; denote by Ii a row vector where the i-th element is 1 and all of the other elements are zeros, i.e., Ii = (0, 0, ..., 1, ..., 0). We use H[ci] to represent the power level of a candidate location ci . Before giving some explanations about TCA, we first con￾sider the following variant of the P3 problem (VP3 ): For each candidate location ci , we are given L chargers with constant but exactly different power levels, i.e., the power levels of these Algorithm 3 Two-Choice-based Approx. Alg. for P3 (TCA) Input: C, S, and B Output: C ′ and H 1: Z ← C × H 2: Z1 ← ∅, H1 ← 0 3: while B ≥ min (ci ,hk )∈Z\Z1 p(hk) + ∑ (ci ,hk )∈Z1 p(hk) do 4: (c, h) ← arg max (c,h)∈Z\Z1, ∑ (ci ,hk )∈Z1∪{(c,h)} p(hk )≤B Q(Z1 ∪ {(c, h)}) − Q(Z1) 5: Z1 ← Z1 ∪ {(c, h)} 6: if H1[c] < h then H1[c] ← h 7: end while 8: (C ′ 1 , H1) ←RemoveDuplicationAndUtilize(C,S, B, H1) 9: Z2 ← ∅, H2 ← 0 10: while B ≥ min (ci ,hk )∈Z\Z2 p(hk) + ∑ (ci ,hk )∈Z2 p(hk) do 11: (c, h) ← arg max (c,h)∈Z\Z2, ∑ (ci ,hk )∈Z2∪{(c,h)} p(hk )≤B Q(Z2∪{(c,h)})−Q(Z2) p(h) 12: Z2 ← Z2 ∪ {(c, h)} 13: if H2[c] < h then H2[c] ← h 14: end while 15: (C ′ 2 , H2) ←RemoveDuplicationAndUtilize(C,S, B, H2) 16: return arg max (C′ ,H)∈{(C ′ 1 ,H1),(C ′ 2 ,H2)} Q(C ′ , H) 17: 18: Sub-procedure: RemoveDuplicationAndUtilize 19: Input: C, S, B, and H 20: Output: C ′ and H 21: C ′ ← ∅, B ′ ← 0 22: for all H[ci] > 0 do 23: C ′ ← C′ ∪ {ci}, B ′ ← B ′ + p(H[ci]) 24: end for 25: while B − B ′ ≥ pmin do 26: ci ← arg max H[ci]+1≤L Q(C ′ ∪ {ci}, H + Ii) − Q(C ′ , H) 27: C ′ ← C′ ∪ {ci}, H[ci] ← H[ci] + 1, B ′ ← B ′ + pmin 28: end while 29: return (C ′ , H) chargers are 1, 2, ..., and L. We use (ci , hk) to denote the charger of a constant power level hk that can only be placed at ci . Note that there are, in total, N·L chargers. Given a power budget B, how do we find a charger placement that maximize the objective function defined below? Let Z be the Cartesian product of C and H; denote by Z′ a subset of Z. We redefine several functions for the VP3 problem via overloading. The power p(ci , sj , hk) received by device sj from ci (its power level is hk) is p(ci , sj , hk) =    α (d(ci ,sj)+β) 2 p(hk) d(ci , sj) ≤ D(hk), 0 d(ci , sj) > D(hk). (7) Correspondingly, given a charger placement Z′ , the to￾tal power pZ′ (sj) received by device sj is pZ′ (sj) = ∑ (ci ,hk )∈Z′ p(ci , sj , hk). The charging quality of Z′ on sj is QZ′ (sj) = min{pZ′ (sj), Pj}. (8)