Symbol Meaning Hardness the number of candidate locations P3 with fixed the set of candidate locations analysis power levels C a charger placement,i.e.,a subset of C Ci a candidate location or a charger P the power of charger ci P3 in a cyde hi the power level of charger c Pth the threshold of negligible power Fig.3:Flowchart of our solution Pmin the minimum power of a charger L the maximum power level of a charger D(hi) the maximum coverage radius with respect to h; H■ a power allocation,i.e.,(hi,h2,...,hN) IV.SOLUTION TO P3 M the number of stationary devices Fig.3 shows the flowchart of our solution.In this section, S the set of stationary devices Si an energy consuming device we first show that p3 is NP-complete,then we propose Pi the maximum power consumption rate of device sj an approximation algorithm for a simplified case of the p3 B the power budget problem,where the power level of each candidate location is d(c.s)the distance between charger ci and device s; fixed,and finally we present aapproximation algorithm p(Ci,si) the power received by device s;from charger ci for the p3 problem.We also discuss an extension of p3 and Pc(si) the total power received by si with respect to C Qo(si) the charging quality of C on device s, propose a provably good solution to it. Q(C.H)the charging quality with respect to C'and H A.Hardness Analysis Fig.2:Main notations for quick reference. Theorem 1:The p3 problem is NP-complete Proof:We prove this theorem by reduction from the Set We assume the power received by one device from multiple Cover problem(SC)[13].which is NP-complete.The decision chargers is additive [9].That is,given a charger placement C', version of the SC problem is as follows:Given a universe the total power pc(s;)received by device s;is u=le1,e2,m of m elements and an integer y,a collection of subsets of u.R =[R1.R2,....Rl,does there exist a sub- pe(s)=∑ptG,s (3) collection of R of size y that covers all elements of w? CIEC Given an instance of the decision version of the SC problem. we construct an instance of the P3 problem as follows.We let For example,in Fig.1,if we set C=(c1,c2)and H=(2,2),L=1,i.e.,every charger can only operated at the fixed power we have pc(s1)=p(c1,51)+p(c2,51),Pc(s2)=p(c1,52),and Pmin.For each element ej in u,we construct a device sj Pc(s3)=p(c2,53). in p3.We assume that all devices have the same maximum power consumption rate,i.e.,P1=P2 =...,=Pm =P.For C.Problem Definition each RER,we add a candidate location c;to P3.For each element ej in Ri,we move sj into the coverage of ci.We also The maximum power consumption rate of device s;is make sure that,as long as a device s;is within the coverage represented by Pj.If the total power pc(sj)received by device of a location ci,p(ci,sj)>P;this can be achieved by setting sj is larger than Pj.the over-received power,i.e.,pc(sj)-Pj. Pmin to a sufficiently large value. would be useless.Therefore,we define the charging quality Combining these together,we get the following special case Qc(sj)of C'on device sj as: of the decision version of the P3 problem:Given a candidate location set C of size k.and a device set S of size m,does Qc(s）=minlPc(s,Pl (4) there exist a charger placement Cof sizesuch that QC,(1,1,,1)≥mP? Main notations are summarized in Fig.2 for quick reference. It is not hard to see that the construction can be finished in We define our objective function as follows: polynomial time;thus,we reduce solving the NP-complete SC Definition I:(Charging Quality)Given a charger place-problem to solving a special case of the P3 problem,implying ment C'and a power allocation H,the charging quality,denot- that p3 is NP-hard.It is easy to verify that P3 is in NP;the ed as (C',H),is defined as the sum of the charging qualities theorem follows immediately. ■ of C'and H on all devices,i.e..(C'.H)=c(sj) The main problem studied in this paper is: B.Approximation Algorithm for p3 with Fixed Power Levels Problem 1:(Charger Placement and Power Allocation In this subsection,we study the p3 problem where the Problem,P3)Given a set C of candidate locations,a set S charger at each location can only work at a fixed power of devices,and a power budget B.p3 is to find a charger level,ie..h is constant for all candidate locations.The placement C'and a power allocation H to maximize Q(C',H), approximation algorithms designed here will serve as basics subject to the power budget constraint,ie..Ec Pis B. of the algorithm for p3 proposed in the next subsection.Symbol Meaning N the number of candidate locations C the set of candidate locations C ′ a charger placement, i.e., a subset of C ci a candidate location or a charger pi the power of charger ci hi the power level of charger ci pth the threshold of negligible power pmin the minimum power of a charger L the maximum power level of a charger D(hi) the maximum coverage radius with respect to hi H a power allocation, i.e., (h1, h2, ..., hN) M the number of stationary devices S the set of stationary devices sj an energy consuming device Pj the maximum power consumption rate of device sj B the power budget d(ci , sj) the distance between charger ci and device sj p(ci , sj) the power received by device sj from charger ci pC′ (sj) the total power received by sj with respect to C ′ QC′ (sj) the charging quality of C ′ on device sj Q(C ′ , H) the charging quality with respect to C ′ and H Fig. 2: Main notations for quick reference. We assume the power received by one device from multiple chargers is additive [9]. That is, given a charger placement C ′ , the total power pC′ (sj) received by device sj is pC′ (sj) = ∑ ci∈C′ p(ci , sj). (3) For example, in Fig. 1, if we set C ′ = {c1, c2} and H = (2, 2), we have pC′ (s1) = p(c1, s1)+ p(c2, s1), pC′ (s2) = p(c1, s2), and pC′ (s3) = p(c2, s3). C. Problem Definition The maximum power consumption rate of device sj is represented by Pj . If the total power pC′ (sj) received by device sj is larger than Pj , the over-received power, i.e., pC′ (sj)− Pj , would be useless. Therefore, we define the charging quality QC′ (sj) of C ′ on device sj as: QC′ (sj) = min{pC′ (sj), Pj}. (4) Main notations are summarized in Fig. 2 for quick reference. We define our objective function as follows: Definition 1: (Charging Quality) Given a charger place￾ment C ′ and a power allocation H, the charging quality, denot￾ed as Q(C ′ , H), is defined as the sum of the charging qualities of C ′ and H on all devices, i.e., Q(C ′ , H) = ∑M j=1 QC′ (sj) The main problem studied in this paper is: Problem 1: (Charger Placement and Power Allocation Problem, P3 ) Given a set C of candidate locations, a set S of devices, and a power budget B, P3 is to find a charger placement C ′ and a power allocation H to maximize Q(C ′ , H), subject to the power budget constraint, i.e., ∑ ci∈C′ pi ≤ B. P 3 with fixed power levels P 3 Hardness analysis P 3 in a cycle Fig. 3: Flowchart of our solution. IV. Solution to P 3 Fig. 3 shows the flowchart of our solution. In this section, we first show that P3 is NP-complete, then we propose an approximation algorithm for a simplified case of the P3 problem, where the power level of each candidate location is fixed, and finally we present a 1−1/e 2L -approximation algorithm for the P3 problem. We also discuss an extension of P3 and propose a provably good solution to it. A. Hardness Analysis Theorem 1: The P3 problem is NP-complete. Proof: We prove this theorem by reduction from the Set Cover problem (SC) [13], which is NP-complete. The decision version of the SC problem is as follows: Given a universe U = {e1, e2, ..., em} of m elements and an integer y, a collection of subsets of U, R = {R1,R2, ...,Rk}, does there exist a sub￾collection of R of size y that covers all elements of U? Given an instance of the decision version of the SC problem, we construct an instance of the P3 problem as follows. We let L = 1, i.e., every charger can only operated at the fixed power pmin. For each element ej in U, we construct a device sj in P3 . We assume that all devices have the same maximum power consumption rate, i.e., P1 = P2 = ..., = Pm = P. For each Ri ∈ R, we add a candidate location ci to P3 . For each element ej in Ri , we move sj into the coverage of ci . We also make sure that, as long as a device sj is within the coverage of a location ci , p(ci , sj) ≥ P; this can be achieved by setting pmin to a sufficiently large value. Combining these together, we get the following special case of the decision version of the P3 problem: Given a candidate location set C of size k, and a device set S of size m, does there exist a charger placement C ′ of size ⌊ B pmin ⌋, such that Q(C ′ , (1, 1, ..., 1)) ≥ mP? It is not hard to see that the construction can be finished in polynomial time; thus, we reduce solving the NP-complete SC problem to solving a special case of the P3 problem, implying that P3 is NP-hard. It is easy to verify that P3 is in NP; the theorem follows immediately. B. Approximation Algorithm for P3 with Fixed Power Levels In this subsection, we study the P3 problem where the charger at each location can only work at a fixed power level, i.e., hi is constant for all candidate locations. The approximation algorithms designed here will serve as basics of the algorithm for P3 proposed in the next subsection