## 5 Reducing the Size of \(\mathcal{D}^{Y}_{I,\epsilon}\)
* During the \(3\)rd period, when \(\tau_{\text{cur}}\in I_{3}\), \(\mathcal{E}^{Y}_{I,\epsilon}\) maintains \(\mathcal{D}^{Y}_{I_{3},\epsilon}\) in addition to \(\mathcal{D}^{Y}_{I_{2},\epsilon}\). Also, the \(\mathcal{D}^{Y}_{I_{1},\epsilon}=\langle\mathcal{C}_{J_{1},\lambda,\kappa(c_ {1})},\ldots,\mathcal{C}_{J_{m},\lambda,\kappa(c_{m})}\rangle\) is consolidated into \(\mathcal{C}_{I_{1},\lambda,\frac{1}{\epsilon}}\). * In general, during the \(i\)th period, when \(\tau_{\text{cur}}\in[(i-1)d_{\max}+1,id_{\max}]=I_{i}\), \(\mathcal{E}^{Y}_{I,\epsilon}\) maintains \(\mathcal{D}^{Y}_{I_{i-1},\epsilon}\) and \(\mathcal{D}^{Y}_{I_{i},\epsilon}\), and also \(\mathcal{C}_{I_{1..i-2},\lambda,\frac{1}{\epsilon}}\) where \(I_{1..i-2}=I_{1}\cup I_{2}\cup\cdots\cup I_{i-2}\). Observe that in this period, there is no item \((a,u)\) with \(u\in I_{1..i-2}\) arrives (because the tardiness is \(d_{\max}\)), and thus we do not need to update \(\mathcal{C}_{I_{1..i-2},\lambda,\frac{1}{\epsilon}}\). However, we will keep throwing away any node \(N\) in \(\mathcal{C}_{I_{1..i-2},\lambda,\frac{1}{\epsilon}}\) as soon as we know \(i(N)\) is to the left of \(p_{\text{max}}+1\). * When entering the \((i+1)\)st period, we do the followings: Keep \(\mathcal{D}^{Y}_{I_{i},\epsilon}\), create \(\mathcal{D}^{Y}_{I_{i+1},\epsilon}\), merge \(\mathcal{C}_{I_{1..i-2},\lambda,\kappa}\) with \(\mathcal{D}^{Y}_{I_{i-1},\epsilon}=\langle\mathcal{C}_{J_{1},\lambda,\kappa(c_ {1})}\ldots,\mathcal{C}_{J_{m},\lambda,\kappa(c_{m})}\rangle\), and then get \(\mathcal{C}_{I_{1..i-1},\lambda,\frac{1}{\epsilon}}\) by consolidating \(\langle\mathcal{C}_{I_{1..i-2},\lambda,\frac{1}{\epsilon}},\mathcal{C}_{J_{1}, \lambda,\kappa(c_{1})}\ldots,\mathcal{C}_{J_{m},\lambda,\kappa(c_{m})}\rangle\). Given any \(t\in[p_{\mathtt{max}}+1,r_{I}]\), the estimate of \(f_{a}([t,r_{I}])\) given by \(\mathcal{E}^{Y}_{I,\epsilon}\) is  
\[\hat{f}_{a}([t,r_{I}])=v(\mathsf{alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{ a})\]  
The following theorem gives the accuracy of \(\hat{f}_{a}([t,r_{I}])\), \(\mathcal{E}^{Y}_{I,\epsilon}\)'s size and its update time. **Theorem 8**: __  
1. _For any_ \(t\in[p_{\mathtt{max}}+1,r_{I}]\)_, the estimate_ \(\hat{f}_{a}([t,r_{I}])\) _given by_ \(\mathcal{E}^{Y}_{I,\epsilon}\) _satisfies_ \[f_{a}([t,r_{I}])-2\epsilon Y\leq\hat{f}_{a}([t,r_{I}])\leq f_{a}([t,r_{I}])+2\epsilon Y\]
2. \(\mathcal{E}^{Y}_{I,\epsilon}\) _has size_ \(O(\frac{1}{\epsilon}(\log\log d_{\max})\log d_{\max})\)_, and supports_ \(O(\log\frac{1}{\epsilon}+\log\log d_{\max})\) _update time._  
Recall that \(I\) is partitioned into sub-intervals \(I_{1},I_{2},\dots,I_{m}\). Suppose that \(t\in I_{k}\). Note that if we had not performed any consolidation,  
\[v(\mathsf{alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})=v(\mathsf{alive} (\mathcal{D}^{Y}_{I_{k},\epsilon})_{\geq t}^{a})+\sum_{k+1\leq i\leq m}v( \mathsf{alive}(\mathcal{D}^{Y}_{I_{i},\epsilon})^{a})\]  
Note that for \(k+1\leq i\leq m\), \(v(\mathsf{alive}(\mathcal{D}^{Y}_{I_{i},\epsilon})^{a})\leq f_{a}(I_{i})\), and for \(v(\mathsf{alive}(\mathcal{D}^{Y}_{I_{k},\epsilon})_{\geq t}^{a})\), since \(|I_{k}|=d_{\max}\), the same argument used in the proof of Lemma 3 gives us \(v(\mathsf{alive}(\mathcal{D}^{Y}_{I_{k},\epsilon})_{\geq t}^{a})\leq f_{a}([t,r_{I_{k}}])+\lambda\log d_{\max}\). Hence  
\[v(\mathsf{alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})=v( \mathsf{alive}(\mathcal{D}^{Y}_{I_{k},\epsilon})_{\geq t}^{a})+\sum_{k+1\leq i \leq m}v(\mathsf{alive}(\mathcal{D}^{Y}_{I_{i},\epsilon})^{a})\\ \leq f_{a}([t,r_{I_{k}}])+\lambda\log d_{\max}+\sum_{k+1\leq i \leq m}f_{a}(I_{i})=f_{a}([t,r_{I}])+\lambda\log d_{\max} \tag{10}\]  
The consolidation step may add errors to \(v(\mathsf{alive}(\mathcal{E}^{Y}_{I,\epsilon})_{\geq t}^{a})\). To get a bound on them, let \(N_{1},N_{2},\dots\) be the nodes for \(a\) in \(\mathcal{E}^{Y}_{I,\epsilon}\), ordered from left to right. Suppose that \(t\in N_{h}\).