# A Note on a Fully Polynomial-Time Approximation Scheme for Minimizing Makespan of Deteriorating Jobs

Authors: Long Wan
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

In (1998), Kovalyov and Kubiak studied the problem of schedulingn deteriorating jobs on a single machine to minimize makespan. They presented a fully polynomial-time approximation scheme which is based on a dynamic programming. Unfortunately, their dynamic programming is incorrect. So the fully polynomial-time approximation scheme is also invalid. In this paper, we construct an instance to show how their dynamic programming does not work and provide a correct dynamic programming, based on which a new fully polynomial-time approximation scheme is derived.


---

## Body

## 1. Introduction

For most scheduling problems, the job processing times are fixed parameters whenever they start. However, such restrictive assumptions do not hold in some environments of financial management, steel production, resource allocation, national defense, and so forth, where the jobs can deteriorate when they are delayed. To the best of our knowledge, Brown and Yechiali [1] and Kunnathur and Gupta [2] initiated the problems of scheduling the deteriorating jobs nonpreemptively. They mainly considered the single-machine makespan problems with job deterioration. Mosheiov [3] first concerned the job deterioration single-machine scheduling problem for which the only machine is available at any given time point. Chen [4] extended the study to the parallel-machine scheduling problem for which the objective is to minimize the total completion time of the jobs. He showed that it is ordinarily NP-hard when the number of the machines is fixed and strongly NP-hard when the number of the machines is input. Ji and Cheng [5] considered the parallel-machine scheduling problem with the objective to minimize the makespan and showed that the problem is ordinarily NP-hard when the number of the machines is fixed and strongly NP-hard when the number of the machines is input. Wu and Lee [6] first studied the deteriorating job scheduling problem under the machine availability constraint condition. For more papers about this topic, the reader is referred to Fan et al. [7], Ji et al. [8], and Li and Fan [9].In this paper, we revisit the following single machine scheduling problem with bounded deterioration introduced in [10]. There are n independent jobs that need to be processed on a single machine. The machine is continuously available for processing from time zero onwards, and it can process at most one job at a time. Each job Jj has a basic processing time denoted by pj,  j=1,2,…,n. The jobs have a given common critical dated after which they start to deteriorate and a common maximum deterioration dateD  (d<D<∞) after which the jobs deteriorate no further. The actual processing time aj(t) of job Jj is stated as follows:
(1)aj(t)={pj,ift≤d,pj+wj(t-d),ifd<t<D,pj+wj(D-d),ift≥D.
Here wj≥0 is the deterioration rate of job Jj and t denotes the start time of job Jj. Without loss of generality, we assume that d, D, pj, wj are integral. The problem is to schedule the jobs to minimize makespan Cmax, that is, the completion time of the last job. Following the notation in Kovalyov and Kubiak [11], we denote this problem by DET for simplicity.For problemDET, Kovalyov and Kubiak [11] presented a dynamic programming and a fully polynomial-time approximation scheme (FPTAS). Unfortunately, their dynamic programming is incorrect. So their FPTAS is also invalid.In this paper, we construct an instance to show how their dynamic programming does not work and provide a correct dynamic programming, based on which a new FPTAS is derived.The rest of this paper is constructed as follows. We first give some preliminary knowledge in Section2. In Section 3, we give a counterexample and show that the dynamic programming in [11] does not work. In Section 4, we provide a correct dynamic programming based on which an FPTAS is presented.


## 2. Preliminaries

Letε be a positive number. An algorithm Aϵ for problem DET is a (1+ϵ)-approximation algorithm if CA≤(1+ϵ)C* for all instances, where C* is the optimal makespan and CA is the makespan obtained by the algorithm. A family of (1+ϵ)-approximation algorithm {Aϵ} defines a fully polynomial-time approximation scheme (FPTAS for short), if for any ϵ>0, Aϵ runs in time bounded by a polynomial of n, L, and 1/ϵ, where L=logmax{n,D,1/ϵ,pmax,wmax} is the number of bits in the binary encoding of the largest numerical parameter in the input with pmax=max1≤j≤n{pj} and wmax=max1≤j≤n{wj}. In the sequel, we may assume 0<ϵ≤1.We can assume that∑j=1n‍pj>d. Otherwise, the problem becomes trivial. Furthermore, if there is idle time on the machine in any schedule, we can eliminate the idle time and shorten the makespan of the schedule. So a schedule can be determined by a permutation of jobs. Under the two conditions, for any given schedule, there is a unique job that starts by time d and completes after time d. We call such a job pivotal. Any job that starts before d and completes by d is called early, any job that starts after d but by D is called tardy, and any job that starts after D is called suspended. For each job Jk, we write sVk=max{d+1,pk} and sUk=d+pk. If Jk is a pivotal job with completion time s, then sVk≤s≤sUk. Thus, sVk and sUk are the lower bound and upper bound of the pivotal job Jk, respectively.For a given jobJk and an integer s with sVk≤s≤sUk, let DET(k,s) be the restricted DET problem in which the pivotal job is Jk and the completion time of Jk is s. Notice that there must exist a pair (k*,s*) with k*∈{1,2,…,n} and sVk*≤s*≤sUk*, such that the optimal solution of the restricted problem DET(k*,s*) is also optimal for problem DET. Thus problem DET can be reduced to the solving of these restricted problems DET(k,s) with k=1,2,…,n and s=sVk,sVk+1,…,sUk. Notice that the number of the restricted problems is exponential in the size of problem DET.To guarantee that each restricted problemDET(k,s) (1≤k≤n, sVk≤s≤sUk) has a solution, we allow the machine to be idle before the starting time of the first job in a schedule of DET(k,s). Then the total processing time of the early jobs is upper bounded by s-pk in every feasible schedule of problem DET(k,s).For a fixed jobJk, let s* and s′ be two time points such that sVk≤s*<s′≤sUk and s′-s*≤δ(s*-d), where 0<δ≤1. Let x* and x′ be the optimal solutions to the restricted problems DET(k,s*) and DET(k,s′), respectively. The following lemma shows that we will have only a little loss if we use x′ instead of x* as a solution of problem DET(k,s*).Remark 1.
The following two lemmas are established in Kovalyov and Kubiak [11]. We present more clarified proofs for completion.Lemma 2.
C
max
(
x
′
)
≤
(
1
+
δ
)
C
max
(
x
*
).Proof.
Recall thatsVk≤s*≤s′≤sUk. Then the total processing time of the early jobs in x* is upper bounded by s*-pk≤s′-pk≤d. Let x- be the schedule obtained from x* by shifting the processing of all jobs right so that Jk completes at time s′. Then Jk is also the pivotal job in x-, and the starting time of the earliest tardy job (if any) in x- is s′. Since x- is a feasible solution of DET(k,s′), we have Cmax(x′)≤Cmax(x-). Note that the suspended jobs in x* remain suspended in x-. Suppose that (J1,J2,…,Jl) be the order of the tardy jobs in x*. Let pj* and pj- be the actual processing time of job Jj in x* and x-, respectively, j=1,2,…,l. Then
(2)p1--p1*≤w1t0=t1,p2--p2*≤w2(t0+t1)=t2,⋮pl--pl*≤wl(t0+t1+⋯+tl-1)=tl,
where t0=s′-s*. This means that each Jj is postponed at most ∑i=1j-1‍ti to be processed in x-, j=1,2,…,l. Therefore,
(3)Cmax(x′)-Cmax(x*)≤Cmax(x-)-Cmax(x*)≤∑i=0l‍ti=∏i=1l‍(1+wi)(s′-s*).
On the other hand, since J1 starts at s* in solution x*, we have
(4)p1*≥w1r0=r1,p2*≥w2(r0+r1)=r2,⋮pl*≥wk(r0+r1+⋯+rl-1)=rl,
where r0=s*-d. Hence,
(5)Cmax(x*)≥r0+∑j=1k‍pj*≥∑j=0l‍rj=∏i=1l‍(1+wi)r0.
Note that s′-s*≤δ(s*-d)=δr0. Then we have
(6)Cmax(x′)≤Cmax(x*)+∏i=1l‍(1+wi)(s′-s*)≤Cmax(x*)+δ∏i=1k‍(1+wi)r0≤(1+δ)Cmax(x*).
The lemma follows.By Lemma2, we may first partition [sVk,sUk] into hk subintervals [tik,ti+1k] such that ti+1k-tik≤δ(tik-d), i=0,1,…,hk-1, where hk≤log(1+δ)pk+1. Let x^ be the best solution among the optimal solutions of the restricted problems DET(k,s), k=1,2,…,n, s=t1k,t2k,…,thkk and let xopt be the optimal solution of DET. Then we have Cmax(x^)≤(1+δ)Cmax(xopt). Note that the number of these subproblems is at most n+(nL/δ) which is polynomial in the size of the input and 1/δ. So if we have an FPTAS for each restricted problem DET(k,s), then we can get an FPTAS for DET. We form the conclusion in the following lemma.Lemma 3.
If one has an FPTAS for every restricted problemDET(k,s), then one can get an FPTAS for DET.Proof.
We apply the an FPTAS for each of the restricted problemsDET(k,s), k=1,2,…,n, s=t1k,t2k,…,thkk within a factor of 1+δ. Let x¨ be the best output solution. By Lemma 2, we can easily deduce
(7)Cmax(x¨)≤(1+δ)2Cmax(xopt)≤(1+ϵ)Cmax(xopt),
where δ=ϵ/3≤1. The lemma follows.By Lemma3, we only need to design an FPTAS for any given restricted problem DET(k,s). Given the pivotal job Jk and the completion time s of Jk, we use r=pk to denote the processing time of job Jk and reindex the remaining n-1 jobs according to Smith’s rule [12] such that w1/p1≥w2/p2≥⋯≥wn-1/pn-1. By a simple exchange of pairwise consecutive jobs, we can show that the tardy jobs is sequenced by Smith’s rule in the optimal schedule. Note that the actual processing time of early jobs and suspended jobs are unchanged. So the orders of early jobs and suspended jobs do not matter. It follows that there exists an optimal schedule in which the early jobs are sequenced arbitrarily, followed by the pivotal job, followed by the tardy jobs sequenced by Smith’s rule, and followed by the suspended jobs sequenced arbitrarily.


## 3. Counterexample

First we demonstrate the dynamic programming adopted by [11]. The authors introduced the 0-1 variables xj,j=1,2,…,n-1, where xj=0 means that Jj is early and xj=1 means that Jj is tardy or suspended. Let X be the set of all 0-1 vectors x=(x1,x2,…,xn-1). Set
(8)F0(x)=s,G0(x)=s-d,P0(x)=0,Fj(x)=Fj-1(x)+xj(pj+wjGj-1(x)),Gj(x)=min{Fj(x),D}-d,Pj(x)=∑i=1j‍pi(1-xi),
where x∈X and j=1,2,…,n-1. Note that neither Fj  nor   Gj nor Pj depends on xj+1,…,xn-1. Pj(x) is the total processing time of early jobs from the job set {J1,J2,…,Jj}. Obviously, we should have Pj(x)≤s-r. If Jj starts at Fj-1(x)≥s, then it is tardy or suspended and its start delay is Gj-1(x). Consequently, Jj finished at Fj(x)=Fj-1(x)+pj+wjGj-1(x). If Jj is scheduled early, then it does not change the makespan, and so, Fj(x)=Fj-1(x). Thus, problem DET(k,s) reduces to the following programming:
(9)min{Fn-1(x)}s.t.00Pn-1(x)≤s-r,x∈X.If we require that all of the tardy and suspended jobs are processed in the nonincreasing order of Smith’s ratios, programming (9) does work. Unfortunately, for problem DET(k,s), the requirement cannot guarantee the optimality. Then programming (9) above is invalid to solve problem DET(k,s).Consider the following job instance. We have three jobsJ1, J2, J3 with p1=11, p2=13, and p3=15 and w1=10, w2=11, and  w3=12,  d=0 and D=20. Since d=0, there are three restricted problems DET(1,11), DET(2,13), and DET(3,15). Note that w1/p1>w2/p2>w3/p3.ForDET(1,11), programming (9) schedules the jobs in the order J1≺J2≺J3 consecutively on the machine with makespan 400. But if we schedule the jobs in the order J1≺J3≺J2 on the machine, the makespan is 391<400.ForDET(2,13), programming (9) schedules the jobs in the order J2≺J1≺J3 consecutively on the machine with makespan 409. But if we schedule the jobs in the order J2≺J3≺J1 on the machine, the makespan is 395<409.ForDET(3,15), programming (9) schedules the jobs in the order J3≺J1≺J2 consecutively on the machine with makespan 409. But if we schedule the jobs in the order J3≺J2≺J1 on the machine, the makespan is 404<409.So the solution forDET via programming (9) has makespan 400. But the optimal solution for DET has makespan 391.


## 4. Dynamic Programming and FPTAS

We are now ready to formulate the recursive equations forDET(k,s). In a feasible schedule x for DET(k,s) the n-1 jobs other than Jk are partitioned into E(x), T(x), and S(x), where E(x) is the set of all early jobs, T(x) is the set of all tardy jobs, and S(x) is the set of all suspended jobs. Recall that r=pk, and the n-1 jobs other than Jk have been reindexed according to Smith’s rule such that w1/p1≥w2/p2≥⋯≥wn-1/pn-1.We introduce the variablesxj∈{-1,0,1}, j=1,2,…,n-1, where xj=-1 if Jj is (assumed to be) early and put into job set E(x), xj=0 if Jj is (assumed to be) tardy and put into job set T(x), and xj=1 if Jj is (assumed to be) suspended and put into job set S(x). Then each vector x=(x1,x2,…,xn-1) represents a schedule (may be infeasible) of DET(k,s). Let X={-1,0,1}n-1 be the set of all vectors x=(x1,x2,…,xn-1) with xj∈{-1,0,1}, 1≤j≤n-1. Set
(10)E0(x)=0,Ej(x)=Ej-1(x)+12xj(xj-1)pj,T0(x)=s,Tj(x)=Tj-1(x)+(1+xj)(1-xj)×(pj+wj(Tj-1(x)-d)),S0(x)=0,Sj(x)=Sj-1(x)+12xj(1+xj)(pj+wj(D-d)),
where x∈X and j=1,2,…,n-1.Givenx∈X, it can be observed that Ej(x), Tj(x), and Sj(x) only depend on x1,x2,…,xj. We overload the notations Ej(x), Tj(x), and Sj(x) so that they also represent the sets of all early jobs, all tardy jobs and all suspended jobs, respectively, among the first j jobs J1,…,Jj. Then Ej(x) is the total processing time of the jobs in Ej(x), Tj(x) is the last completion time of the jobs in Tj(x), and Sj(x) is the total processing time of the jobs in Sj(x). We say that an x∈X is a quasi-feasible schedule if En-1(x)≤s-r. Note that the condition En-1(x)≤s-r means that we should have enough time space to schedule the early jobs before the pivotal job Jk. The objective value of a quasi-feasible schedule x is defined to be Cmax(x)=Tn-1(x)+Sn-1(x).For a quasi-feasible schedule vectorx, we can process the jobs in En-1(x) starting at time s-r-En-1(x), followed by the pivotal job Jk, followed by the jobs in Tn-1(x), and then followed by the jobs in Sn-1(x), consecutively. The real schedule generated by this way is denoted by x~. We call x~ the real schedule corresponding to x. We can observe that En-1(x)=E(x~) for every quasi-feasible schedule x. In the case that Tn-1(x)=T(x~) and Sn-1(x)=S(x~), we just have x=x~.Generally, a quasi-feasible schedulex may not be a feasible schedule, since Tn-1(x) (or Sn-1(x)) may not be the set of tardy jobs (or the set of suspended jobs) in x~. But the following lemma enables us to focus the attention on the quasi-feasible schedules.Lemma 4.
For each quasi-feasible schedulex, one has Cmax(x)≥Cmax(x~), and furthermore, the equality holds if and only if x=x~.Proof.
SinceCmax(x)=Tn-1(x)+Sn-1(x), we only need to show that Cmax(x~)≤Tn-1(x)+Sn-1(x). Note that En-1(x)=E(x~). We distinguish the following two cases.(i)
Tn-1(x)<D. Then Tn-1(x)⊆T(x~) and S(x~)⊆Sn-1(x). For each Jj∈Tn-1(x)∪S(x~), the actual processing time of Jj in x~ is equal to the contribution of Jj for Tn-1(x)+Sn-1(x) when Jj is considered. For each Jj∈Sn-1(x)∩T(x~), the actual processing time of Jj in x~ is less than the contribution of Jj for Tn-1(x)+Sn-1(x) when Jj is considered. Therefore, Cmax(x~)≤Tn-1(x)+Sn-1(x) with equality holding if and only if Sn-1(x)=∅, that is, Tn-1(x)=T(x~) and Sn-1(x)=S(x~)=∅.(ii)
Tn-1(x)≥D. Then Sn-1(x)⊆S(x~) and T(x~)⊆Tn-1(x). For each Jj∈Sn-1(x)∪T(x~), the actual processing time of Jj in x~ is equal to the contribution of Jj for Tn-1(x)+Sn-1(x) when Jj is considered. For each Jj∈Tn-1(x)∩S(x~), the actual processing time of Jj in x~ is less than the contribution of Jj for Tn-1(x)+Sn-1(x) when Jj is considered. Therefore, Cmax(x~)≤Tn-1(x)+Sn-1(x) with equality holding if and only if Tn-1(x)∩S(x~)=∅, that is, Tn-1(x)=T(x~) and Sn-1(x)=S(x~). The lemma follows.The result of Lemma4 implies that an optimal quasi-feasible schedule of problem DET(k,s) is also an optimal schedule of the same problem. Thus problem DET(k,s) can be reduced to the following programming:
(11)min{Sn-1(x)+Tn-1(x)}s.t.00Rn-1(x)≤s-r,x∈X.Theorem 5.
Programming (11) solves problem DET(k,s) correctly in O(nd(pmax+wmax(D-d))(wsum(D-d)+psum))=O(n2d(pmax+wmax(D-d))2) time.Proof.
The correctness of programming (11) is implied in the previous discussion.
In each iteration of programming (11), we generate the values Ej(x), Tj(x), and Sj(x) from Ej-1(x), Tj-1(x), and Sj-1(x). To save the space, we only need to consider the states so that Ej(x)≤s-r and Tj(x)≤D+pmax+wmax(D-d). Here, Ej(x)≤s-r means that we only consider the quasi-feasible schedules, and Tj(x)≤D+pmax+wmax(D-d) means that any job starting at or after time D+pmax+wmax(D-d) should be a suspended job.
WriteVj=(Ej(x),Tj(x),Sj(x)):  x∈X,  Ej(x)≤s-r,  Tj(x)≤D+pmax+wmax(D-d),  j=0,1,…,n-1. Since Ej(x)≤s-r<d,  d<s≤Tj(x)≤D+pmax+wmax(D-d), and Sj≤psum+wsum(D-d), we have |Vj|<d(D-d+pmax+wmax(D-d))(psum+wsum(D-d)). Then |V0|+|V1|+⋯+|Vn-1|<nd(D-d+pmax+wmax(D-d))(psum+wsum(D-d))<2nd(pmax+wmax(D-d))(psum+wsum(D-d)). Consequently, the time complexity of programming (11) is upper bounded by O(nd(pmax+wmax(D-d))(psum+wsum(D-d))). The lemma follows.To construct the FPTAS, we employ a procedure calledpartition(A,H,v), where A is a set of vectors, H is a nonnegative function in the vectors x∈A, and 0<v<1 is a positive number.Procedure
p
a
r
t
i
t
i
o
n
(
A
,
H
,
v
)
(i)
Arrange vectorsx∈A in order x(1),x(2),…,x(|A|) such that 0≤H(x(1))≤H(x(2))≤⋯≤H(x(|A|)).
(ii)
Assign vectorsx(1),x(2),…, one by one to set A1H until we meet the first index i1 such that H(x(i1))≤(1+v)H(x(1))<H(x(i1+1)). If such an i1 does not exist, then set A1H=A and stop.
(iii)
Assign vectorsx(i1+1),x(i1+2),…, one by one to set A2H until we meet the first index i2 such that H(x(i2))≤(1+v)H(x(i1+1))<H(x(i2+1)). If such an i2 does not exist, then set A2H=A∖A1H and stop.
(iv)
Continue the above procedure untilx(|A|) is included in ArHH for some rH.Assume that the calculation ofH(x) needs a constant time for each x∈A. Procedure partition(A,H,v) requires O(|A|log|A|) time to arrange elements of A in nondecreasing order of H(x) and O(|A|) time to produce the partition. Then the total complexity of procedure partition(A,H,v) is O(|A|log|A|).The two lemmas in the following are straightforward and can be found in [11].Lemma 6.
|
H
(
x
)
-
H
(
x
′
)
|
≤
v
min
{
H
(
x
)
,
H
(
x
′
)
} for any x,x′∈AlH,l=1,2,…,rH.Lemma 7.
r
H
≤
log
(
1
+
v
)
H
(
x
(
|
A
|
)
)
+
2
≤
(
2
log
H
(
x
(
|
A
|
)
)
/
v
)
+
2 for 0<v<1 and H(x(|A|))≥1.Based on procedure partition, we will provide an FPTAS, called AlgorithmAδ(k,s) for the restricted problem DET(k,s). The algorithm is formally stated below.Algorithm
A
δ
(
k
,
s
)
(1)
(Initialization) Reindex the jobs except the pivotal job by Smith’s rule such thatw1/p1≥w2/p2≥⋯≥wn-1/pn-1. Set Y1={(-1),(0),(1)} and j=2.
(2)
(Generation ofY2,Y3,…,Yn-1) Generate set Yj′ by assigning -1,0 or 1 to the jth coordinate of vectors from Yj-1, that is, Yj′={(x,xj)∣x∈Yj-1,xj∈{-1,0,1}}.
Calculate the following for anyx∈Yj′:
E
j
(
x
)
=
E
j
-
1
(
x
)
+
(
1
/
2
)
x
j
(
x
j
-
1
)
p
j,
T
j
(
x
)
=
T
j
-
1
(
x
)
+
(
1
+
x
j
)
(
1
-
x
j
)
(
p
j
+
w
j
(
T
j
-
1
(
x
)
-
d
)
), and
S
j
(
x
)
=
S
j
-
1
(
x
)
+
(
1
/
2
)
x
j
(
1
+
x
j
)
(
p
j
+
w
j
(
D
-
d
)
).
IfEj(x)>s-r for some x∈Yj′, then delete x from Yj′.
Ifj>n-1, go to 3.
Ifj≤n-1, then set v=δ/2n and perform the following computations:
callpartition(Yj′,Tj-d,v) to partition set Yj′ into disjoint subsets Y1T,Y2T,…,YrTjT.
callpartition(Yj′,Sj,v) to partition set Yj′ into disjoint subsets Y1S,Y2S,…,YrSjS.
Divide setYj′ into disjoint subsets Yab=YaT∩YbS, a=1,2,…,rTj; b=1,2,…,rSj.
In each nonempty subsetYab, choose a vector x(ab) such that Ej(x(ab))=min{Ej(x):x∈Yab}.
SetYj={x(ab):Yab≠∅, a=1,2,…,rTj; b=1,2,…,rSj}, and j=j+1, go to 2.
(3)
(Solution) Select vectorx0∈Yn-1 such that
(12)Tn-1(x0)+Sn-1(x0)=min{Tn-1(x)+Sn-1(x):x∈Yn-1}.We now show that the vectorx0 returned by Algorithm Aδ(k,s) has the objective value at most 1+δ multiples of the objective value of the optimal vector of programming (11). Let π0=x~0 be the real schedule corresponding to x0, and let π* be the optimal schedule for DET(k,s). Then we have the following lemma.Lemma 8.
C
max
(
π
0
)
≤
(
1
+
δ
)
C
max
(
π
*
).Proof.
From Lemma4, let x*=(x1*,x2*,…,xn-1*) be the optimal vector of programming (11); we know Cmax(π0)≤Tn-1(x0)+Sn-1(x0) and Tn-1(x*)+Sn-1(x*)≤Cmax(π*). It is sufficient to show that Tn-1(x0)+Sn-1(x0)≤(1+δ)Tn-1(x*)+Sn-1(x*).
In the following, we will show that there exists a vectorx(j)∈Yj which meets the following three conditions by induction for j=1,2,…,n-1:(1)
Ej(x(j))≤Ej(x*)≤s-r,(2)
|Tj(x(j))-Tj(x*)|≤vj(Tj(x*)-d)≤vjTj(x*),(3)
|Sj(x(j))-Sj(x*)|≤vjSj(x*), where v0=0 and vj=v+(1+v)vj-1, j=1,2,…,n-1.
Whenj=1, (x1*)∈Y1. By setting x(1)=(x1*), the previous three conditions hold apparently.
Inductively, suppose thatj≤n-1, and there exists a vector x(j-1)∈Yj-1 which meets the previous three conditions for index j-1. Then we have (x(j-1),xj*)∈Yj′.
Letx(j-)=(x(j-1),xj*) for simplicity, x(j-)∈Yj′. Then,
(13)Ej(x(j-))=Ej-1(x(j-1))+12xj*(xj*-1)pj≤Ej-1(x*)+12xj*(xj*-1)pj=Ej(x*),(14)|Tj(x(j-))-Tj(x*)|=|Tj-1(x(j-1))-Tj-1(x*)0+(1+xj*)(1-xj*)0×wj(Tj-1(x(j-1))-Tj-1(x*))|=(1+(1+xj*)(1-xj*)wj)×|Tj-1(x(j-1))-Tj-1(x*)|≤(1+(1+xj*)(1-xj*)wj)×vj-1(Tj-1(x*)-d)≤vj-1(Tj(x*)-d),
where the last inequality follows the fact (1+(1+xj*)(1-xj*)wj)(Tj-1(x*)-d)≤  (1+(1+xj*)(1-xj*)wj)(Tj-1(x*)-d)+(1+xj*)(1-xj*)pj=Tj(x*)-d, and
(15)|Sj(x(j-))-Sj(x*)|=|Sj-1(x(j-1))-Sj-1(x*)|≤vj-1Sj-1(x*)≤vj-1Sj(x*).
Since x(j-)∈Yj′, by the algorithm and Lemma 6, there exists x(j)∈Yj such that
(16)Ej(x(j))≤Ej(x(j-)),(17)|Tj(x(j))-Tj(x(j-))|0000=|(Tj(x(j))-d)-(Tj(x(j-))-d)|0000≤v(Tj(x(j-))-d),(18)|Sj(x(j))-Sj(x(j-))|≤v(Sj(x(j-))).
From (13) and (16), we have Ej(x(j))≤Ej(x*). From (14) and (17), we have
(19)|Tj(x(j))-Tj(x*)|≤|Tj(x(j))-Tj(x(j-))|+|Tj(x(j-))-Tj(x*)|≤v(Tj(x(j-))-d)+vj-1(Tj(x*)-d)≤v(1+vj-1)(Tj(x*)-d)+vj-1(Tj(x*)-d)=vj(Tj(x*)-d),
where the last inequality follows from the fact Tj(x(j-))-d≤|Tj(x(j-))-Tj(x*)|+Tj(x*)-d≤(1+vj-1)(Tj(x*)-d). Similarly, by (15) and (18), we get |Sj(x(j))-Sj(x*)|≤vjSj(x*). Note that vn-1=(1+v)n-1-1≤ev(n-1)-1<eδ/2-1≤δ for 0<δ<1. So
(20)Tn-1(x0)+Sn-1(x0)=Tn-1(x0)+Sn-1(x0)-(Tn-1(x*)+Sn-1(x*))+(Tn-1(x*)+Sn-1(x*))≤Tn-1(x(n-1))+Sn-1(x(n-1))-(Tn-1(x*)+Sn-1(x*))+(Tn-1(x*)+Sn-1(x*))≤vn-1(Tn-1(x*)+Sn-1(x*))+(Tn-1(x*)+Sn-1(x*))≤(1+δ)(Tn-1(x*)+Sn-1(x*)).
This completes the proof.Now, we consider the time complexity of AlgorithmAδ(k,s). Note that s≤Tj(x)≤s+∑j=1n-1‍(pj+wj(D-d)) and 0≤Sj(x)≤∑j=1n-1‍(pj+wj(D-d)) for each j and each x. Actually, we can get Tj(x)≤D+pmax+wmax(D-d), because once Tj(x)≥D, we may set xj+1=xj+2=⋯=xn=0; that is, we do not put Jj+1,Jj+2,…,Jn into Tj+1(x). Hence, by Lemma 7, |Yj|≤(2log(D+pmax+wmax(D-d))+2)(2log(∑j=1n-1‍(pj+wj(D-d)))+2)=O(L2/δ2). Therefore, the complexity of Algorithm Aδ(k,s) is O(nL3/δ2). Note that there are at most O(nL/δ) restricted problems DET(k,s). Herefore, by Lemmas 4 and 8, we can get a (1+ϵ)-approximation solution in O(n2L4/δ3)=O(n2L4/ϵ3) time.



---

*Source: 957494-2013-09-11.xml*