ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2841 connections to r;are declared covered,and r;is the ▣ra ▣ covering host for each of them. When all devices become covered,the first half of PDA terminates. positive OSg 5.4.2 Compute Integral Primal Solution Closely covered Normally covered Loosely covered The second part of PDA computes an integral solution to Fig.4.Three types of being covered(See lines 26-33 of Alg.PDA).Note ISCA-MP-T.In fact,the as and Bs obtained from the first that a positive connection is also full,but a full connection may be not half of PDA give us some clues for finding an integral solu- positive. tion to ISCA-MP-T. 9citii Initially,each rij is 0;each yi is 0;each itinerary is not finally selected (fselected).Ris is the set of temporarily R10 +> ri∈R8eS 10店/， selected itineraries.In fact,Rts contains some unnecessary itineraries.In lines 23-25,we select a subset of Rt as the finally in terms of∑aj According to Alg.PDA,each device is covered by one of the selected itineraries.We first construct a graph G with Ris as three types (see lines 26-33):closely covered (ccovered),nor- vertex set.For each pair of ri,r&E Rts,there is an edge mally covered (ncovered),and loosely covered (lcovered).Fig.4 between them if and only if 3sj ES,s.t.positivej=positivekj gives an illustration,where squares represent itineraries. =1.Then we find a maximal independent vertex set in G,say For each ccovered device sj,we suppose that ri covers it in D,as the set of finally selected itineraries.D is obtained as fol- the final solution.Since the connection between ri and s;is lows:we sort the vertex set of G in non-decreasing order of positive, and then check whether each vertex(i.e.,itinerary)can be aj can be split into two parts:Bij and added into the maximal set.The itinerary selection part is (fij+9citi/(10T))(lines 9,and 13-14).It is trivial to see that done.The rest of the task is itinerary association. (15) For each sj,we denote Rj as the set of temporarily selected itineraries that have positive connections to s;(line 8 is ccovered,and r:∈D rex 10 27).There are three cases: and the second part of aj pays for the connection cost, If RinD0,since D is a maximal independent ver- 9citij tex set on G,RinD has only one element,say ri; -B= 10T: thus we set rij-1,and sj is called closely covered; sj is ccovered,andh∈D Ti∈R sj is ccovered ● Otherwise,the covering host of sj,say rk,is in D.We (16) setj-1,and sj is called normally covered; For each ncovered device sj,we suppose that rk covers it In the remaining case,D must contain rh such that r in the final solution.Since the connection between r and sj and rh are neighbors in G,and ch/Th ck/T is full,a;pays for the connection cost, (because D is a maximal independent set,again);we then set hj-1,and sj is called loosely covered. 9citij (17) 10T sj is ncovered,and r:ED 5.4.3 Dual Feasibility For lcovered devices,we have the following theorem: We have to check whether the obtained as and Bs satisfy the four constraints in Eq.(13).Constraints(13(e))and (13(d)) Theorem 3.For lcovered devices,we have are trivial.In lines 13-14,whenever a;is larger than .9y≥T 9citij fwe also increase by one,making sure con- 10T straint (13(c))is not violated.In lines 15-18,whenever (18) all uncovered devices that have full connec- Proof.For each lcovered device sj,we suppose that rh cov- tions to ri will be marked as covered,implying that those ers it in the final solution and that rk is its covering host Bi,s will not increase any more. (see Fig.4).According to line 23 of Alg.PDA,there must exist another sg that has positive connections with both rk 5.4.4 Primal Feasibility and rh.It is trivial to see that We check whether the obtained as and ys violate the four con- a;≥fs+9ckt/(10Tk), straints in Eq.(14).For Eq.(5 e),lines 26-33 of PDA guarantee that each s;is charged by one of the finally selected itineraries. a&g≥fg+9ctg/(10Tk), For Eg.(5f),lines 26-33 guarantee that devices can only be ag fhg +9chthg/(10Th). charged by the finally-selected itineraries.The rest is trivial. We denote by tsh and tsk the timestamps when rh and rk are marked as temporarily selected (line 16),respec- 5.4.5 Approximation Ratio Analysis tively.Since rk is the covering host of sj,we have We denote by OPT the optimal solution to ISCA-MP-T.Due aj tsk.Since the connection between sg and either rh or to the weak duality theorem [331is a lower bound rk is positive,we have agz min(tsh,tsk).Therefore, of OPT.We now try to find a upper bound of 0j20gconnections to ri are declared covered, and ri is the covering host for each of them. When all devices become covered, the first half of PDA terminates. 5.4.2 Compute Integral Primal Solution The second part of PDA computes an integral solution to ISCA-MP-T. In fact, the as and bs obtained from the first half of PDA give us some clues for finding an integral solu￾tion to ISCA-MP-T. Initially, each xij is 0; each yi is 0; each itinerary is not finally selected (fselected). Rts is the set of temporarily selected itineraries. In fact, Rts contains some unnecessary itineraries. In lines 23-25, we select a subset of Rts as the finally selected itineraries. We first construct a graph G with Rts as vertex set. For each pair of ri; rk 2 Rts, there is an edge between them if and only if 9sj 2 S, s.t. positiveij ¼ positivekj ¼ 1. Then we find a maximal independent vertex set in G, say D, as the set of finally selected itineraries. D is obtained as fol￾lows: we sort the vertex set of G in non-decreasing order of ci Ti and then check whether each vertex (i.e., itinerary) can be added into the maximal set. The itinerary selection part is done. The rest of the task is itinerary association. For each sj, we denote Rj as the set of temporarily selected itineraries that have positive connections to sj (line 27). There are three cases: If Rj \ D 6¼ ;, since D is a maximal independent ver￾tex set on G, Rj \ D has only one element, say ri; thus we set xij 1, and sj is called closely covered; Otherwise, the covering host of sj, say rk, is in D. We set xkj 1, and sj is called normally covered; In the remaining case, D must contain rh such that rk and rh are neighbors in G, and ch=Th ck=Tk (because D is a maximal independent set, again); we then set xhj 1, and sj is called loosely covered. 5.4.3 Dual Feasibility We have to check whether the obtained as and bs satisfy the four constraints in Eq. (13). Constraints (13(e)) and (13(d)) are trivial. In lines 13-14, whenever aj is larger than fij þ 9citij 10Ti , we also increase bij by one, making sure con￾straint (13(c)) is not violated. In lines 15-18, whenever P sj2S bij ¼ ci 10, all uncovered devices that have full connec￾tions to ri will be marked as covered, implying that those bijs will not increase any more. 5.4.4 Primal Feasibility We check whether the obtained xs and ys violate the four con￾straints in Eq. (14). For Eq. (5 e), lines 26-33 of PDA guarantee that each sj is charged by one of the finally selected itineraries. For Eq. (5f), lines 26-33 guarantee that devices can only be charged by the finally-selected itineraries. The rest is trivial. 5.4.5 Approximation Ratio Analysis We denote by OPT the optimal solution to ISCA-MP-T. Due to the weak duality theorem [33], P sj2S aj is a lower bound of OPT. We now try to find a upper bound of X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij; in terms of P sj2S aj. According to Alg. PDA, each device is covered by one of the three types (see lines 26-33): closely covered (ccovered), nor￾mally covered (ncovered), and loosely covered (lcovered). Fig. 4 gives an illustration, where squares represent itineraries. For each ccovered device sj, we suppose that ri covers it in the final solution. Since the connection between ri and sj is positive, aj can be split into two parts: bij, and ðfij þ 9citij=ð10TiÞÞ (lines 9, and 13-14). It is trivial to see that X sj is ccovered; and ri2D bij ¼ X ri2R ciyi 10 ; (15) and the second part of aj pays for the connection cost, X sj is ccovered; and ri2D aj  bij ¼ X ri2R X sj is ccovered fij þ 9citij 10Ti xij: (16) For each ncovered device sj, we suppose that rk covers it in the final solution. Since the connection between rk and sj is full, aj pays for the connection cost, X sj is ncovered; and ri2D aj ¼ X ri2R X sj is ncovered fij þ 9citij 10Ti xij: (17) For lcovered devices, we have the following theorem: Theorem 3. For lcovered devices, we have X sj is lcovered; and ri2D 9aj  X ri2R X sj is lcovered fij þ 9citij 10Ti  xij: (18) Proof. For each lcovered device sj, we suppose that rh cov￾ers it in the final solution and that rk is its covering host (see Fig. 4). According to line 23 of Alg. PDA, there must exist another sg that has positive connections with both rk and rh. It is trivial to see that aj  fkj þ 9cktkj=ð10TkÞ; ag  fkg þ 9cktkg=ð10TkÞ; ag  fhg þ 9chthg=ð10ThÞ: We denote by tsh and tsk the timestamps when rh and rk are marked as temporarily selected (line 16), respec￾tively. Since rk is the covering host of sj, we have aj  tsk. Since the connection between sg and either rh or rk is positive, we have ag  minðtsh; tskÞ. Therefore, aj  ag. Fig. 4. Three types of being covered (See lines 26-33 of Alg. PDA). Note that a positive connection is also full, but a full connection may be not positive. ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2841