Algorithm 1 The Greedy Placement Algorithm(GPA) Input:C,S,B,and p Output:C C 8N-1 1:C←0 N-1 S1 2:while C1<Lg」do 3: c-arg max (Q(C'U(c))-Q(C')) CEC\C C←C'U{c ●S2 5:end while ●S3 SN- 6:return C SN (a)Using Equ.(5) (b)Using Equ.(6) 1)Uniform Case:We first look at the uniform case of Fig.4:Motivational examples show that,directly applying Equ.(5)or Equ.(6) to the non-uniform case may perform very bad. power levels,i.e.,h=h2 =...=hN =h.In other words, P1 =p2 =...=PN p(h)=h.Pmin.For convenience,denote the power of each charger by p in this subsection. ·Pc(si）≤Pj:in this case,we have In this case,the objective function (C,H)degenerates into (C),and the P3 problem can be reformulated as follows: Qcuten(sj)-Qc(sj)=min(Pj-Pc(sj),p(c.sj). Given a set C of candidate locations,a set S of devices. Qcue(s）-Qc(s）=min(Pi-Pc(p(c,sh. a power budget B.and a fixed power p,p3 is to find a charger placement C'to maximize O(C),subject to the budget Ifpc,si）≤Pj-Pc(s,then constraint,ie.,IC 2cuc(s）-Qc(s）=pc,sj）=Qcue(si）-Qc.(s In the following,we prove that the objective function (C) has three tractable properties:nonnegativity,monotonicity, If Pi-Pc"(sj)<p(c,sj)<Pj-Pc(sj).then and submodularity,which enable us to propose a(1-1/e)- Qcuc(s）-Qc(s)=pc,s approximation algorithm shown in Alg.1. Definition 2:(Nonnegativity,Monotonicity,and Submod- >Pj-Pc(s）=Qcue(s）-Qc(sj ularity)Given a non-empty finite set and a function f IfPi-Pc(s）≤pc,s),then defined on the power set 2u of U with real values,f is called nonnegative if f(列）≥0 for all Acu;f is called monotone Q(cuten(sj)-Qc(sj)=Pj-Pc(sj) if f(A)<f(A')for all AcA U:f is called submodular ≥Pj-Pc(si）=Qcuc(si)-Qc(s) iffU{e)-f(列≥f(A'U{e)-f')for all Ac A'cu Therefore,we proved that Q(C')is submodular. ■ We have the following theorem: According to the results in [21,22],we have a(1-1/e)- Theorem 2:The objective function O(C')is nonnegative, approx.algorithm shown in Alg.1,which starts with an empty monotone,and submodular. set C',in each iteration,we add the location that maximizes Proof:According to Def.1,O(C')is nonnegative.For all the marginal gain of the objective function into C,i.e., C'C"CC,we have Qc)=∑%cs∑c-(=Qc c-arg max (Q(C'U(c))-Q(C)). (5) CEC\C There are at most N iterations in Alg.1;in each iteration, implying that,(C)is monotone.For all C'C"C,we we need to check at most N locations to find the location that need to prove Q(C'U (c))-Q(C')>Q(C"U(cl)-Q(C").It maximizes the marginal gain.It takes O(MN)time to compute is sufficient to show that for any sieS,we have (C),thus,the time complexity of Alg.1 is O(MN3). Qcue(s）-Qc(s）≥Qicrule(s）-Qc(sj: 2)Non-uniform Case:We then study the non-uniform case of power levels,in this case,P3 can be reformulated as follows: Based on Equ.(3)and Equ.(4),we prove the above inequation Given a set C of candidate locations,a set S of devices,a in three cases: power budget B,and a power allocation H=(h,h2....,hN). ·Pj≤Pc(si:since Pc(si)≥Pc(sid,we have p3 is to find a charger placement C'to maximize (C).subject Qcuc(s）-Qc(s）=0=Qcuc(s）-Qc(s. to the budget constraint,.ie,∑c,ecpi≤B. To solve this problem,an intuitive method is using the same ·Pc(si）<P)j<Pc(sl:in this case,Qicule(s）- greedy idea as in Equ.(5).However,we show in Fig.4(a)that, Oc"(sj)=0,and we have this method may perform very bad.In Fig.4(a),there are N=L+1 candidate locations and M=N devices:h=h2= Qcue(si）-Qc(si) ...hN-1=1,and hN =L;the radii of dashed circles indicate =min(P,-Pc(si,Pcuc(si）-Pc(s》 the maximum coverage distance of each charger;p(c1,s)= =min(P,-Pc(spc,s》 p(c2,52)=...=p(cN-1,SN-1)=p(cN,SN)-E,where e satisfies 20=Qc"uen(si）-Qc(s 0<E<p(CN,SN).Given a power budget B =L.Pmin,usingAlgorithm 1 The Greedy Placement Algorithm (GPA) Input: C, S, B, and p Output: C ′ 1: C ′ ← ∅ 2: while |C′ | < ⌊ B p ⌋ do 3: c ← arg max c∈C\C′ (Q(C ′ ∪ {c}) − Q(C ′ )) 4: C ′ ← C′ ∪ {c} 5: end while 6: return C ′ 1) Uniform Case: We first look at the uniform case of power levels, i.e., h1 = h2 = ... = hN = h. In other words, p1 = p2 = ... = pN = p(h) = h · pmin. For convenience, denote the power of each charger by p in this subsection. In this case, the objective function Q(C ′ , H) degenerates into Q(C ′ ), and the P3 problem can be reformulated as follows: Given a set C of candidate locations, a set S of devices, a power budget B, and a fixed power p, P3 is to find a charger placement C ′ to maximize Q(C ′ ), subject to the budget constraint, i.e., |C′ | ≤ ⌊ B p ⌋. In the following, we prove that the objective function Q(C ′ ) has three tractable properties: nonnegativity, monotonicity, and submodularity, which enable us to propose a (1 − 1/e)- approximation algorithm shown in Alg. 1. Definition 2: (Nonnegativity, Monotonicity, and Submod￾ularity) Given a non-empty finite set U, and a function f defined on the power set 2U of U with real values, f is called nonnegative if f(A) ≥ 0 for all A ⊆ U; f is called monotone if f(A) ≤ f(A′ ) for all A ⊆ A′ ⊆ U; f is called submodular if f(A∪ {e})− f(A) ≥ f(A′∪ {e})− f(A′ ) for all A ⊆ A′ ⊆ U. We have the following theorem: Theorem 2: The objective function Q(C ′ ) is nonnegative, monotone, and submodular. Proof: According to Def. 1, Q(C ′ ) is nonnegative. For all C ′ ⊆ C′′ ⊆ C, we have Q(C ′ ) = ∑M j=1 QC′ (sj) ≤ ∑M j=1 QC′′ (sj) = Q(C ′′), implying that, Q(C ′ ) is monotone. For all C ′ ⊆ C′′ ⊆ C, we need to prove Q(C ′ ∪ {c}) − Q(C ′ ) ≥ Q(C ′′ ∪ {c}) − Q(C ′′). It is sufficient to show that for any sj ∈ S, we have Q(C′∪{c})(sj) − QC′ (sj) ≥ Q(C′′∪{c})(sj) − QC′′ (sj). Based on Equ. (3) and Equ. (4), we prove the above inequation in three cases: • Pj ≤ PC′ (sj): since PC′′ (sj) ≥ PC′ (sj), we have Q(C′∪{c})(sj) − QC′ (sj) = 0 = Q(C′′∪{c})(sj) − QC′′ (sj). • PC′ (sj) < Pj < PC′′ (sj): in this case, Q(C′′∪{c})(sj) − QC′′ (sj) = 0, and we have Q(C′∪{c})(sj) − QC′ (sj) = min{Pj − PC′ (sj), P(C′∪{c})(sj) − PC′ (sj)} = min{Pj − PC′ (sj), p(c, sj)} ≥ 0 = Q(C′′∪{c})(sj) − QC′′ (sj). c1 s1 c2 s2 cN-1 sN-1 cN sN (a) Using Equ. (5) c1 s1 c2 s2 s3 sN-1 sN (b) Using Equ. (6) Fig. 4: Motivational examples show that, directly applying Equ. (5) or Equ. (6) to the non-uniform case may perform very bad. • PC′′ (sj) ≤ Pj : in this case, we have Q(C′∪{c})(sj) − QC′ (sj) = min{Pj − PC′ (sj), p(c, sj)}, Q(C′′∪{c})(sj) − QC′′ (sj) = min{Pj − PC′′ (sj), p(c, sj)}. If p(c, sj) ≤ Pj − PC′′ (sj), then Q(C′∪{c})(sj) − QC′ (sj) = p(c, sj) = Q(C′′∪{c})(sj) − QC′′ (sj). If Pj − PC′′ (sj) < p(c, sj) < Pj − PC′ (sj), then Q(C′∪{c})(sj) − QC′ (sj) = p(c, sj) > Pj − PC′′ (sj) = Q(C′′∪{c})(sj) − QC′′ (sj). If Pj − PC′ (sj) ≤ p(c, sj), then Q(C′∪{c})(sj) − QC′ (sj) = Pj − PC′ (sj) ≥ Pj − PC′′ (sj) = Q(C′′∪{c})(sj) − QC′′ (sj). Therefore, we proved that Q(C ′ ) is submodular. According to the results in [21, 22], we have a (1 − 1/e)- approx. algorithm shown in Alg. 1, which starts with an empty set C ′ , in each iteration, we add the location that maximizes the marginal gain of the objective function into C ′ , i.e., c ← arg max c∈C\C′ (Q(C ′ ∪ {c}) − Q(C ′ )). (5) There are at most N iterations in Alg. 1; in each iteration, we need to check at most N locations to find the location that maximizes the marginal gain. It takes O(MN) time to compute Q(C ′ ), thus, the time complexity of Alg. 1 is O(MN3 ). 2) Non-uniform Case: We then study the non-uniform case of power levels, in this case, P3 can be reformulated as follows: Given a set C of candidate locations, a set S of devices, a power budget B, and a power allocation H = (h1, h2, ..., hN), P 3 is to find a charger placement C ′ to maximize Q(C ′ ), subject to the budget constraint, i.e., ∑ ci∈C′ pi ≤ B. To solve this problem, an intuitive method is using the same greedy idea as in Equ. (5). However, we show in Fig. 4(a) that, this method may perform very bad. In Fig. 4(a), there are N = L + 1 candidate locations and M = N devices; h1 = h2 = ... = hN−1 = 1, and hN = L; the radii of dashed circles indicate the maximum coverage distance of each charger; p(c1, s1) = p(c2, s2) = ... = p(cN−1, sN−1) = p(cN, sN)−ϵ, where ϵ satisfies 0 < ϵ < p(cN, sN). Given a power budget B = L · pmin, using