## 5 Reducing the Size of \(\mathcal{D}^{Y}_{I,\epsilon}\)
As argued previously, any node in \(\textsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq p}\) is in some \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}_{\geq p}\). Below, we show that for any \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}_{\geq p}\), we can make at most \(\frac{\epsilon Y}{2\log W}\) debit operations to the queue \(Q^{a}_{J,\lambda}\) of \(\mathcal{C}_{J,\lambda,\kappa}\) during its lifespan. Together with the fact that \(|\textsc{All}_{\geq p}|\leq 2\log W\), we have \(d(\textsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq p}^{a})\leq\epsilon Y\). Consider any \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}_{\geq p}\). Note that the smaller its capacity, the larger the number of debit operations can be made to the queue \(Q^{a}_{J,\lambda}\) of \(\mathcal{C}_{J,\lambda,\kappa}\). To maximize the number of debit operations made to \(Q^{a}_{J,\lambda}\), suppose that \(v_{J}=0\) and thus \(\mathcal{C}_{J,\lambda,\kappa}\) has the smallest capacity \(\kappa(1)\) when it is created. Before increasing its capacity to \(\kappa(2)\), \(\mathcal{C}_{J,\lambda,\kappa}\) can make at most \(\frac{1}{\kappa(1)}\cdot\frac{Y}{\log W}\) debit operations to \(Q^{a}_{J,\lambda}\). Then, during the next \(\frac{Y}{\log W}\) arrivals of items \((a,u)\) with \(u\in J\), \(\frac{Y}{\log W}\leq v_{J}+\bar{f}_{*}(J)<\frac{2Y}{\log W}\), the capacity is \(\kappa(2)\), and at most \(\frac{1}{\kappa(2)}\cdot\frac{Y}{\log W}\) debit operations can be made to \(Q^{a}_{J,\lambda}\). In general, during the period when \(\frac{(c-1)Y}{\log W}\leq v_{J}+\bar{f}_{*}(J)<\frac{cY}{\log W}\), at most \(\frac{1}{\kappa(c)}\cdot\frac{Y}{\log W}\) debit operations can be made to \(Q^{a}_{J,\lambda}\). If the largest capacity is \(\kappa(c_{\max})\), the total number of debit operations made to \(Q^{a}_{J,\lambda}\) is at most  
\[\frac{Y}{\log W}(\frac{1}{\kappa(1)}+\cdots+\frac{1}{\kappa(c_{\max})})=\frac{ \epsilon Y}{4(\log\log W)\log W}(1+\frac{1}{2}+\cdots+\frac{1}{c_{\max}})\leq \frac{\epsilon Y(\ln(c_{\max})+1)}{4(\log\log W)\log W}\]  
which is smaller than \(\frac{\epsilon Y}{2\log W}\) because by Equation (9), \(c_{\max}=O(\log W)\), which implies \(\ln(c_{\max})+1\leq 2\log\log W\) (suppose that \(W\) is larger than some constant). We now prove (2). Note that the total number of non-trivial queues in \(\mathcal{D}^{Y}_{I,\epsilon}\), and hence the number of born-poor nodes, is at most \(\sum_{1\leq i\leq m}\kappa(c_{i})=\sum_{1\leq i\leq m}\frac{4c_{i}}{\epsilon} \log\log W\). By Equation (9), \(\sum_{1\leq i\leq m}c_{i}=O(\log W)\), and it follows that the size of \(\mathcal{D}^{Y}_{I,\epsilon}\) is \(O(\frac{1}{\epsilon}\log\log W\log W)\). For the update time, suppose that an item \((a,u)\) arrives. We can find the \(\mathcal{C}_{J_{i},\lambda,\kappa}\) in \(\mathcal{D}^{Y}_{I,\epsilon}=\langle\mathcal{C}_{J_{1},\lambda,\kappa},\ldots, \mathcal{C}_{J_{m},\lambda,\kappa}\rangle\) with \(u\in J_{i}\) using \(O(\log m)=O(\log\log W)\) time by querying a balanced search tree storing the \(J_{i}\)'s. By hashing (e.g., Cuckoo hashing [15], which supports constant update and query time) we can locate the queue \(Q^{a}_{J_{i},\lambda}\in\mathcal{C}_{J_{i},\lambda,\kappa}\) in constant time. Then, by consulting an auxiliary balanced search tree on the intervals monitored by the nodes of \(Q^{a}_{J_{i},\lambda}\), we can find and update the node \(N\) of \(Q^{a}_{J_{i},\lambda}\) with \(u\in i(N)\) using \(O(\log(Y/\lambda))=O(\log\frac{1}{\epsilon}+\log\log W)\) time. At times we may also need to execute Lines 3 and 4 of the procedure \(\text{Process}(\,)\), which debits all the non-trivial queues in \(\mathcal{C}_{J_{i},\lambda,\kappa}\). Using the de-amortizing technique given in [16], this step takes constant time. Note that occasionally, we may also need to clean up \(\mathcal{D}^{Y}_{I,\epsilon}\) by calling \(\text{Trim}(\,)\); this step takes time linear to the size of \(\mathcal{D}^{Y}_{I,\epsilon}\), which is \(O(\frac{1}{\epsilon}\log\log W\log W)\).