2838 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL 16.NO.10,OCTOBER 2017 Intuitively,ISCA-MP is harder to solve than ISCA.To s2,...,sy.Inspired by the performance guarantee analysis help us gain some insights into the problem structure of for the SC problem,we have the following theorem: ISCA-MP,we first study ISCA in Section 4,and we introduce a factor O(In M)approximation algorithm and another sim- Theorem 2.GSA is a factor O(In M)approximation algorithm ple yet practical heuristic algorithm.We then design a factor for ISCA. 10 approximation algorithm for ISCA-MP in Section 5. Proof.We denote by OPT the optimal solution for ISCA and consider the iteration in which s;is covered by ri.At 4 SOLUTION FOR ISCA the beginning of this iteration,IS\S M-j+1;if we In this section,we present a factor O(In M)approximation use the optimal solution to cover remaining devices,the algorithm(Section 4.1)and a practical heuristic(Section 4.2). total energy cost is at most OPT,implying that there exists an unselected itinerary having cost-effectiveness of Alg.GSA(Greedy Selection Algorithm) at mostWe remember that GSA greedily selects the 1.R'-0:S-0 most cost-effective unselected itinerary,so we have 2.ii,x写-0：i,班←-0 3.Vhile S\S≠0do ec(s;)=cost-effectiveness of ri 4. If R R'=0,return failure OPT OPT 5 For each ri∈R\R 6. Compute a subset Si of S\S'by solving ≤5S\SSM-j+T (maxs,s.t∑s,es与≤T) It is obvious to see that the sum of movement-energy 7. '-arg min一 +∑ss and loss-energy used in the solution obtained by GSA is S■ 8. S'←-S'US,andj∈S,ry-1 ∑，esec(s).Since 9. R'-R'ui),and y-1 10.Output rijs and yis ec(s)≤1+ 4.1 Greedy Selection Algorithm ≤OlnM)OPT, The greedy selection algorithm (GSA)is inspired by the reduction from SC to ISCA.The main idea of GSA is to itera- the theorem follows immediately. 0 tively select the most cost-effective itinerary and remove the cov- GSA has at most N iterations.In each iteration,for each ered devices,until all devices are covered.Here,when we say a device is "covered",we mean there is an itinerary that is unselected itinerary,solving the(trivial)knapsack problem requires O(M log M)time,so the overall time complexity is responsible for charging it.""represents set minus.Alg. O(N2M log M). GSA shows the details. R'denotes the set of itineraries that have already been selected,and S'denotes the set of devices that have already 4.2 Modified GSA-A Practical Heuristic Algorithm been covered.Initially,both of them are empty sets.In each GSA has theoretic performance guarantee,but may perform iteration,we first compute the cost-effectiveness of all unse- poorly in practice.This section is devoted to improving lected itineraries and select the most cost-effective one.The GSA from the perspective of practice. cost-effectiveness can be computed as follows. In each iteration of GSA,the most cost-effective itiner- For eachrRR',we want to maximize the number of ary is selected regardless of the other itineraries,devices, uncovered devices that it can cover.Therefore,we have the fol- and their interrelationships.This is the key observation lowing trivialknapsack problem,where S,isasubset of s that helps us improve GSA.The Modified GSA is shown in Alg.MGSA.The difference compared with GSA is marked in blue (lines 6-9).The main idea of MGSA is as max S;l follows. s.t. ∑t场≤ (9) In each iteration,instead of selecting the most cost-effec- BjESi tive itinerary,MGSA selects the itinerary that costs a minimal energy to cover the devices that may take up more energy if they We would like to mention that Eq.(9)is a special case of the are otherwise covered by one of the other unselected itineraries. knapsack problem where the value of each item is 1.There-This intuition is captured by variable gij:for each fore,greedily picking the device with the smallest tij is riR\R'and each sjeS\S,gij is defined as the aver- already optimal and costs only O(Mlog M)time.The cost-age cost of sj if it is covered by the itineraries in effectiveness of r;is then defined as R\(R'U{i}),i.e, 9+∑si f ISil 弱=R1(RUeu We define the energy cost ec(sj)of sjas the cost-effective-Then,for each riR\R',we try to find a subset S;of ness of the itinerary that coverss Without loss of general-uncovered devices that maximizeThus,we have ity,we assume the order in which devices are covered is s1, the following knapsack problem:Intuitively, ISCA-MP is harder to solve than ISCA. To help us gain some insights into the problem structure of ISCA-MP, we first study ISCA in Section 4, and we introduce a factor Oðln MÞ approximation algorithm and another sim￾ple yet practical heuristic algorithm. We then design a factor 10 approximation algorithm for ISCA-MP in Section 5. 4 SOLUTION FOR ISCA In this section, we present a factor Oðln MÞ approximation algorithm (Section 4.1) and a practical heuristic (Section 4.2). Alg. GSA (Greedy Selection Algorithm) 1. R0 ;; S0 ; 2. 8i; j, xij 0; 8i, yi 0 3. While SnS0 6¼ ; do 4. If RnR0 ¼ ;, return failure 5. For each ri 2RnR0 6. Compute a subset Si of SnS0 by solving ðmaxjSij, s.t. P sj2Si tij TiÞ 7. i 0 arg mini ciþ P sj2Si fij jSij 8. S0 S0 [ Si0 , and 8j 2 Si0 , xi0j 1 9. R0 R0 [ fi 0 g, and yi0 1 10. Output xijs and yis 4.1 Greedy Selection Algorithm The greedy selection algorithm (GSA) is inspired by the reduction from SC to ISCA. The main idea of GSA is to itera￾tively select the most cost-effective itinerary and remove the cov￾ered devices, until all devices are covered. Here, when we say a device is “covered”, we mean there is an itinerary that is responsible for charging it. “n” represents set minus. Alg. GSA shows the details. R0 denotes the set of itineraries that have already been selected, and S0 denotes the set of devices that have already been covered. Initially, both of them are empty sets. In each iteration, we first compute the cost-effectiveness of all unse￾lected itineraries and select the most cost-effective one. The cost-effectiveness can be computed as follows. For each ri 2RnR0 , we want to maximize the number of uncovered devices that it can cover. Therefore, we have the fol￾lowing trivial knapsack problem, where Si is a subset of SnS0 : max jSij s.t. X sj2Si tij Ti: (9) We would like to mention that Eq. (9) is a special case of the knapsack problem where the value of each item is 1. There￾fore, greedily picking the device with the smallest tij is already optimal and costs only OðM log MÞ time. The cost￾effectiveness of ri is then defined as ci þ P sj2Si fij jSij : We define the energy cost ecðsjÞ of sj as the cost-effective￾ness of the itinerary that covers sj. Without loss of general￾ity, we assume the order in which devices are covered is s1, s2,..., sM. Inspired by the performance guarantee analysis for the SC problem, we have the following theorem: Theorem 2. GSA is a factor Oðln MÞ approximation algorithm for ISCA. Proof. We denote by OPT the optimal solution for ISCA and consider the iteration in which sj is covered by ri. At the beginning of this iteration, jS n S0 j > M  j þ 1; if we use the optimal solution to cover remaining devices, the total energy cost is at most OPT, implying that there exists an unselected itinerary having cost-effectiveness of at most OPT jSnS0 j . We remember that GSA greedily selects the most cost-effective unselected itinerary, so we have ecðsjÞ ¼ cost-effectiveness of ri OPT jS n S0 j OPT M  j þ 1 : It is obvious to see that the sum of movement-energy and loss-energy used in the solution obtained by GSA is P sj2S ecðsjÞ. Since X sj2S ecðsjÞ 1 þ 1 2 þ ::: þ 1 M OPT Oðln MÞOPT; the theorem follows immediately. tu GSA has at most N iterations. In each iteration, for each unselected itinerary, solving the (trivial) knapsack problem requires OðM log MÞ time, so the overall time complexity is OðN2M log MÞ. 4.2 Modified GSA—A Practical Heuristic Algorithm GSA has theoretic performance guarantee, but may perform poorly in practice. This section is devoted to improving GSA from the perspective of practice. In each iteration of GSA, the most cost-effective itiner￾ary is selected regardless of the other itineraries, devices, and their interrelationships. This is the key observation that helps us improve GSA. The Modified GSA is shown in Alg. MGSA. The difference compared with GSA is marked in blue (lines 6-9).The main idea of MGSA is as follows. In each iteration, instead of selecting the most cost-effec￾tive itinerary, MGSA selects the itinerary that costs a minimal energy to cover the devices that may take up more energy if they are otherwise covered by one of the other unselected itineraries. This intuition is captured by variable gij: for each ri 2RnR0 and each sj 2SnS0 , gij is defined as the aver￾age cost of sj if it is covered by the itineraries in R n ðR0 [ figÞ, i.e., gij ¼ 1 jR n ðR0 [ figÞj X rk2RnðR0 [figÞ fkj: Then, for each ri 2RnR0 , we try to find a subset Si of uncovered devices that maximize P sj2Si gij. Thus, we have the following knapsack problem: 2838 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017