Improved and Parameterized Algorithms for Online Multi-Level Aggregation

In Section 2, we show the following theorem by our memory-based framework.

We emphasize that our algorithm can be directly applied to any tree structure. This makes the analysis direct, and differs from some previous work that relies on reductions to trees with specific structures, such as $L$-decreasing trees [9, 15].

To potentially improve the competitive ratio for MLAP-D, we consider a preferable measure over depth, namely, the caterpillar dimension introduced in [25]. The notion of heavy path decomposition was introduced in [30]. A heavy path decomposition of $𝒯$ is a vertex-disjoint partition $𝒫$ such that (1) each element in $𝒫$ is a set of vertices that contains exactly one leaf vertex and forms a path in $𝒯$ and (2) any two vertices in an element in $𝒫$ must have an ancestor-descendant relationship. Recall that $r$ is the root vertex of $𝒯$. Consider a leaf vertex $u$ and the $r$-$u$ path. Let $d(𝒫,u)$ denote the number of elements in $𝒫$ intersecting the $r$-$u$ path. The dimension of the decomposition $𝒫$ is $dim(𝒫):={\max }_{u\in L(𝒯)}\{d(𝒫,u)\}$ where $L(𝒯)$ denotes the set of leaf vertices in $𝒯$. The caterpillar dimension $H$ of $𝒯$ is the minimum dimension among all heavy path decompositions. See Figure 1 for an example.

The caterpillar dimension remains constant for certain classes of trees, such as line graphs ($H=1$), caterpillar graphs ($H=2$), and lobster graphs ($H=3$). The caterpillar dimension is at most $D$ and ${\log }_2|V|$, and can be computed in polynomial time, as well as the corresponding heavy path decomposition [25].

In Section 3, we show the following theorem using our memory-based framework.

To the best of our knowledge, this is the first online algorithm parameterized on a measure better than depth. Interestingly, our framework outperforms the state-of-the-art ratios of $O(D)$ [16] and $O(\log |V|)$ [4] if $H=o(\min \{D,{\log }_2|V|\})$. For infinite line graphs ($H=1$), the best competitive ratio is known to be exactly 4 [7].

In both the offline and online settings, the fundamental question when designing an algorithm for MLAP-D is to decide how many extra requests to aggregate into the service subtree, beyond the bare minimum required for a feasible solution. The biggest challenge one faces when developing a competitive algorithm is finding a way to lower-bound the performance of the optimum solution for a given instance. Most online algorithms for MLAP-D [9, 15] have been memoryless, in the sense that the algorithm’s decision making is only a function of the current unserved requests and locations, and the relative order of their deadlines. This discards information which can potentially be used to justify further aggregation of the service subtree at a given time $t_i$. Our main algorithmic contribution is to incorporate memory naturally to inform the algorithm’s decision-making process. From a mathematical standpoint, memory is used in the amortized analysis to ensure that we can attribute the cost of our algorithm alg to the cost of the optimal solution opt without double-counting, which is crucial for establishing a competitive ratio.

Leaving out some technical details, we describe the motivations behind our algorithms as follows. When an active request $\rho$ reaches its deadline at time $t_i$, we are forced to transmit a service subtree which contains $v_{\rho }$, and so our algorithm begins by initializing the service subtree as the path $r$-$v_{\rho }$. Each $v$ in the $r$-$v_{\rho }$ path adds a cost of $c(v)$ to the algorithm’s solution, and therefore we want to delay making another service which includes $v$ until we are sure that opt itself must have outputted services with costs comparable to $c(v)$. Therefore, it is natural that each node receives a budget proportional to $c(v)$ which is allocated towards adding extra services to the service subtree, and we call the nodes that the budget is spent on investments. The investment procedure is handled by a recursive function, where deeper nodes are the first to make their investments. The difficulty with this approach is that at different times, several different vertices may invest in the same node, which could lead to over-counting the costs associated with opt.

We use memory to tackle this issue. Before vertices on the path from $r$-$v_{\rho }$ start spending their investment budget, they may also add their previous investments to the service subtree and recursively expand the transmission subtree, in a stage of the algorithm we call the expansion stage. This prevents nodes from reinvesting onto previous investments. The expansion stage is handled by a separate recursive process which occurs before the investment stage. It is then for these expansion vertices that we make investments. We decide whether to add those previous investments as follows. After a vertex has made its investment, we set a timer in memory to record when all of the investments we have made are anticipated to reach their deadline. If a vertex $v$ at time $t_i$ is an expansion vertex again after the timer has elapsed, then we can make inferences about comparable costs opt must have experienced based on our investments. In this case, we call $v$ an anticipated vertex at time $t_i$. Otherwise, we can infer that there must have been a request that had appeared deeper than $v$ and expired before our timer elapsed, which we can also associate with a cost by opt. We call such vertices unanticipated at time $t_i$.

We briefly provide a broad overview of the analysis. In Section 2.1, we express alg in terms of only the unanticipated expansion nodes. We use the standard amortized analysis techniques, in particular, an accounting argument to redistribute the costs in a top-down fashion based on proof by induction. Then in Section 2.2, we show that the unanticipated expansion nodes serve as a way to lower bound opt. This requires using a charging scheme that defines a one-to-one mapping between the cost accounted for the unanticipated expansion vertices and opt. As a consequence of these two results, we can bound the competitive ratio of the algorithm. When we first define the algorithm, we leave a parameter which controls the extent of aggregation unspecified. Selecting the optimal parameter results in an $e(D+1)$-competitive algorithm for MLAP-D.

Our $e(4H+2)$-competitive algorithm utilizes the framework developed by the $e(D+1)$-competitive algorithm. The main difference is the use of the heavy path decomposition structure while assigning memory-based investment budgets to vertices. Instead of assigning the budget for every vertex $v$ to be proportional to its cost $c(v)$, we allow one vertex per path in $𝒫$ to have a potentially much larger budget.

Following the same strategy as before, to prove the competitiveness of our algorithm, we show that (1) the cost alg is comparable with the cost of the unanticipated expansion vertices and (2) we can relate the costs of unanticipated expansion vertices to opt directly via a charging scheme. The charging scheme is identical to our $O(D)$-competitive algorithm. The main change to the analysis is to judiciously modify the redistribution accounting argument for the cost based on a proof by induction to show (1). Ultimately, by selecting the optimal parameters for the two different investment budgets, we obtain an $e(4H+2)$-competitive algorithm for MLAP-D.

The most related variant of MLAP-D is the setting that each request has a waiting cost instead of a strict deadline. The objective is to minimize the sum of the total service and waiting costs. This problem is termed the online multi-level aggregation problem (MLAP). For general MLAP, an algorithm with competitive ratio $D^4{2}^D$ was presented in [7] and later improved to $O(D^2)$ [3]. When $D=1$, MLAP is also called the TCP acknowledgment problem (TCP-AP). The optimal competitive ratio for TCP-AP is 2 for deterministic algorithms [19] and $e/(e-1)\approx 1.582$ for randomized algorithms [16, 20]. Interestingly, TCP-AP is equivalent to the lot sizing problem [31], which has been extensively studied in the operations research community. When $D=2$, MLAP is also called the joint replenishment problem (JRP). The state-of-the-art competitive ratio for JRP is 3 [17] and the current best lower bound is 2.754 [11] which improves an earlier bound of 2.64 [17]. When $H=1$, i.e., the input tree is a line, the upper bound for the competitive ratio is 5 [12] which improves an earlier bound of 8 [14], and the lower bound is 4 [7] which improves an earlier bound of $(5+\sqrt{5})/2\approx 3.618$ [12]. [4] introduced a unifying framework for problems with delay and deadlines admitting a competitive ratio of $O(\log |V|)$ for MLAP. A slight variant of MLAP was presented in [21] where the competitive ratio is logarithmic in the cost of the aggregation tree. We refer the reader to [9] for a concise summary for MLAP and MLAP-D.

In offline MLAP-D, the information of all requests, including the location, the arrival time, and the deadline (also the waiting cost for offline MLAP), is given in advance. The offline problem currently has significantly better approximation results than the online problem. For offline MLAP-D, the current best approximation ratio is 2 [6, 7]. For offline MLAP, the current best approximation ratio is $2+\epsilon$ [28] by adapting an algorithm in [24] for the multi-stage assembly problem. For offline TCP-AP, there is an optimal dynamic programming algorithm [1]. Offline JRP is NP-hard [2] and APX-hard [10, 27] and the current best approximation ratio is 1.791 [11] improving the previous ratios of 1.8 [23] and 2 [24].

Quite surprisingly, the only algorithm parameterized on the caterpillar dimension that we are aware of is the advice complexity of the online $k$-server problem on trees [29]. More specifically, to obtain optimal solutions for online $k$-server on trees, it is sufficient to use $2+2\lceil {\log }_2(H+1)\rceil$ bits of advice per request. We believe that the caterpillar dimension is a natural measure to evaluate the performance of approximation and online algorithms for challenging problems on trees, especially for problems like MLAP-D where the state-of-the-art competitive ratio is linear in the tree depth.

Let $v\in {\overline{A}}_i$ be an unanticipated expansion vertex at time $t_i$. Let ${\rho }_i^{\ast }$ be the request which triggered the creation of a service at time $t_i$, so $d_{{\rho }_i^{\ast }}=t_i$. Using Lemma 16, we know that $v$ is either on the $r$-$v_{{\rho }_i^{\ast }}$ path, or $v\in I_{v^{\ast },i}$ for $v^{\ast }\in A_i$. We thus split the charging scheme into two cases:

• $\mathrm{■}$

  Case 1: $v$ is on the path $r$-$v_{{\rho }_i^{\ast }}$. Then, OPT must have served ${\rho }_i^{\ast }$ within the time $[a_{{\rho }_i^{\ast }},d_{{\rho }_i^{\ast }}]=[a_{{\rho }_i^{\ast }},t_i]$. OPT’s service to ${\rho }_i^{\ast }$ must have also included $v$, and so we charge the cost of $c(v)$ against any of these $c(v)$ costs OPT incurs for including $v$ in its service history within $[a_{{\rho }_i^{\ast }},t_i]$.

• $\mathrm{■}$

  Case 2: $v$ is not on the path $r$-$v_{{\rho }_i}$, and $v\in I_{v^{\ast },i}$ for some $v^{\ast }\in A_i$. If there are multiple such $v^{\ast }$, we simply fix one arbitrarily for each unanticipated $v\in {\overline{A}}_i$. By Lemma 12 we know that $v^{\ast }$ must have been an expansion vertex at a time before $t_i$, so suppose that this occurred most recently at . Then we would have that $nex{t}_{v^{\ast },i^{\ast }}^{\prime }=nex{t}_{v^{\ast },i}$. As $v^{\ast }\in A_i$, we have $nex{t}_{v^{\ast },i}\le t_i$. Now, as $v\in I_{v^{\ast },i}=I_{v^{\ast },i^{\ast }}^{\prime }$ and ALG processes requests in ${𝒯}_{v^{\ast }}$ in non-decreasing deadline, it follows that while ALG was investing the budget on $v^{\ast }$ at time $t_{i^{\ast }}$, there must have been an unserved request $\rho$ on a vertex $v_{\rho }$ such that $v$ was on the path $v^{\ast }$-$v_{\rho }$. Because $nex{t}_{v^{\ast },i^{\ast }}^{\prime }$ is determined as the next pending task in ${𝒯}_u$ not yet in $V_i^E\cup V_i^I$, we know that $d_{\rho }\le nex{t}_{v^{\ast },i^{\ast }}^{\prime }$. Linking this together, we find that $d_{\rho }\le nex{t}_{v^{\ast },i^{\ast }}^{\prime }=nex{t}_{v^{\ast },i}\le t_i$.

  Thus OPT must have served $\rho$ within the time $[a_{\rho },d_{\rho }]$, which is a subset of $[a_{\rho },t_i]$ by the above inequality. Such a service must have included $v$, and thus we charge $c(v)$ to the associated cost of $c(v)$ incurred by OPT during the timeframe $[a_{\rho },t_i]$.

In both Case 1 and Case 2, we find ourselves charging $c(v)$ to a portion of OPT’s service history within $[a_{\rho },t_i]$ which serves $\rho$ where $v_{\rho }$ is deeper than $v$. In order to unify these two cases, we call this particular $\rho$ the request associated with unanticipated node $v$ at time $t_i$.

Using the above charging scheme, the cost of any unanticipated vertex at a time $t_i$ is mapped to a cost in opt. To establish Lemma 7, we are left with showing that this mapping is one-to-one, i.e., no one portion of opt is charged to more than once.