Online Algorithms for Multi-Level Aggregation∗
Marcin Bienkowski†
Christoph Dürr¶

Martin Böhm‡
Jaroslaw Byrka†
Marek Chrobak§
Lukáš Folwarczný‡
Lukasz Jeż†
Jiřı́ Sgall‡

Nguyen Kim Thangk

Pavel Veselý‡

arXiv:1507.02378v3 [] 28 Dec 2016

December 30, 2016
Abstract
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edgeweighted tree T , and have to be served eventually. A service is defined as a subtree X
of T that contains its root. This subtree X serves all requests that are pending in the
nodes of X, and the cost of this service is equal to the total weight of X. Each request
also incurs waiting cost between its arrival and service times. The objective is to minimize
the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a
generalization of some well-studied optimization problems; for example, for trees of depth 1,
MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is
equivalent to the Joint Replenishment Problem. Aggregation problems for trees of arbitrary
depth arise in multicasting, sensor networks, communication in organization hierarchies, and
in supply-chain management. The instances of MLAP associated with these applications are
naturally online, in the sense that aggregation decisions need to be made without information
about future requests.
Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees
of depth more than 2. Addressing this open problem, we give the first constant competitive
online algorithm for trees of arbitrary (fixed) depth. The competitive ratio is O(D4 2D ), where
D is the depth of T . The algorithm works for arbitrary waiting cost functions, including the
variant with deadlines. We include several additional results in the paper. We show that a
standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot
give super-constant lower bounds (as a function of the tree depth). This result is established
by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary
trees. We prove that, in the offline case, these instances can be solved to optimality in polynomial time. We also study the MLAP variant when the tree is a path, for which we give a lower
bound of 4 on the competitive ratio, improving the lower bound known for general MLAP.
We complement this with a matching upper bound for the deadline setting. In addition, for
arbitrary trees, we give a simple 2-approximation algorithm for offline MLAP with deadlines.

1

Introduction

Certain optimization problems can be formulated as aggregation problems. They typically arise
when expensive resources can be shared by multiple agents, who incur additional expenses for
∗ Research

partially supported by NSF grants CCF-1536026, CCF-1217314 and OISE-1157129, Polish NCN
grants DEC-2013/09/B/ST6/01538, 2015/18/E/ST6/00456, project 14-10003S of GA ČR and GAUK project
548214.
† Institute of Computer Science, University of Wroclaw, Poland
‡ Computer Science Institute, Charles University, Czech Republic
§ Department of Computer Science, University of California at Riverside, USA
¶ Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6, Paris, France
k IBISC, Université d’Evry Val d’Essonne, France

1

accessing a resource. For example, costs may be associated with waiting until the resource is
accessible, or, if the resource is not in the desired state, a costly setup or retooling may be
required.
1-level aggregation. A simple example of an aggregation problem is the TCP Acknowledgment
Problem (TCP-AP), where control messages (“agents”) waiting for transmission across a network
link can be aggregated and transmitted in a single packet (“resource”). Such aggregation can
reduce network traffic, but it also results in undesirable delays. A reasonable compromise is to
balance the two costs, namely the number of transmitted packets and the total delay, by minimizing
their weighted sum [17]. Interestingly, TCP-AP is equivalent to the classical Lot Sizing Problem
studied in the operations research literature since the 1950s. (See, for example, [33].) In the offline
variant of TCP-AP, that is when all arrival times of control messages are known beforehand, an
optimal schedule for aggregated packets can be computed with dynamic programming in time
O(n log n) [1]. In practice, however, packet aggregation decisions must be done on the fly, without
any information about future message releases. This scenario is captured by the online variant
of TCP-AP that has also been well studied; it is known that the optimal competitive ratio is 2
in the deterministic case [17] and e/(e − 1) ≈ 1.582 in the randomized case [20, 13, 31]. Online
variants of TCP-AP that use different assumptions or objective functions were also examined in
the literature [18, 2].
2-level aggregation. Another optimization problem involving aggregation is the Joint Replenishment Problem (JRP), well-studied in operations research. JRP models tradeoffs that arise in
supply-chain management. One such scenario involves optimizing shipments of goods from a supplier to retailers, through a shared warehouse, in response to their demands. In JRP, aggregation
takes place at two levels: items addressed to different retailers can be shipped together to the
warehouse, at a fixed cost, and then multiple items destined to the same retailer can be shipped
from the warehouse to this retailer together, also at a fixed cost, which can be different for different retailers. Pending demands accrue waiting cost until they are satisfied by a shipment. The
objective is to minimize the sum of all shipment costs and all waiting costs.
JRP is known to be NP-hard [3], and even APX-hard [28, 7]. The currently best approximation,
due to Bienkowski et al. [8], achieves a factor of 1.791, improving on earlier work by Levi et al. [24,
26, 27]. In the deadline variant of JRP, denoted JRP-D, there is no cost for waiting, but each
demand needs to be satisfied before its deadline. As shown in [7], JRP-D can be approximated
with ratio 1.574.
For the online variant of JRP, Buchbinder et al. [12] gave a 3-competitive algorithm using a
primal-dual scheme (improving an earlier bound of 5 in [11]) and proved a lower bound of 2.64,
that was subsequently improved to 2.754 [8]. The optimal competitive ratio for JRP-D is 2 [8].
Multiple-level aggregation. TCP-AP and JRP can be thought of as aggregation problems on
edge-weighted trees of depth 1 and 2, respectively. In TCP-AP, this tree is just a single edge
between the sender and the recipient. In JRP, this tree consists of the root (supplier), with one
child (warehouse), and any number of grandchildren (retailers). A shipment can be represented by
a subtree of this tree and edge weights represent shipping costs. These trees capture the general
problem on trees of depth 1 and 2, as the children of the root can be considered separately (see
Section 2).
This naturally extends to trees of any depth D, where aggregation is allowed at each level.
Multi-level message aggregation has been, in fact, studied in communication networks in several
contexts. In multicasting, protocols for aggregating control messages (see [10, 4], for example)
can be used to reduce the so-called ack-implosion, the proliferation of control messages routed
to the source. A similar problem arises in energy-efficient data aggregation and fusion in sensor
networks [19, 34]. Outside of networking, tradeoffs between the cost of communication and delay
2

arise in message aggregation in organizational hierarchies [29]. In supply-chain management,
multi-level variants of lot sizing have been studied [16, 22]. The need to consider more tree-like
(in a broad sense) supply hierarchies has also been advocated in [23].
These applications have inspired research on offline and online approximation algorithms for
multi-level aggregation problems. Becchetti et al. [5] gave a 2-approximation algorithm for the
deadline case. (See also [11].) Pedrosa [30] showed, adapting an algorithm of Levi et al. [25] for the
multi-stage assembly problem, that there is a (2 + ε)-approximation algorithm for general waiting
cost functions, where ε can be made arbitrarily small.
In the online case, Khanna et al. [21] gave a rent-or-buy solution (that serves a group of
requests once their waiting cost reaches the cost of their service) and showed that their algorithm
is O(log α)-competitive, where α is defined as the sum of all edge weights. However, they assumed
that each request has to wait at least one time unit. This assumption is crucial for their proof, as
demonstrated by Brito et al. [11], who showed that the competitive ratio of a rent-or-buy strategy
is Ω(D), even for paths with D edges. The same assumption of a minimal cost for a request and
a ratio dependent on the edge-weights is also essential in the work of Vaya [32], who studies a
variant of the problem with bounded bandwidth (the number of packets that can be served by a
single edge in a single service).
The existence of a primal-dual (2 + ε)-approximation algorithm [30, 25] for the offline problem
suggests the possibility of constructing an online algorithm along the lines of [13]. Nevertheless,
despite substantial effort of many researchers, the online multi-level setting remains wide open.
This is perhaps partly due to impossibility of direct emulation of the cleanup phase in primal-dual
offline algorithms in the online setting, as this cleanup is performed in the “reverse time” order.
The case when the tree is just a path has also been studied. An offline polynomial-time
algorithm that computes an optimal schedule was given in [9]. For the online variant, Brito
et al. [11] gave an 8-competitive algorithm. This result was improved by Bienkowski et al. [9] who
showed that the competitive ratio of this problem is between 2 + φ ≈ 3.618 and 5.

1.1

Our Contributions

We study online competitive algorithms for multi-level aggregation. Minor technical differences
notwithstanding, our model is equivalent to those studied in [11, 21], also extending the deadline
variant in [5] and the assembly problem in [25]. We have decided to choose a more generic
terminology to emphasize general applicability of our model and techniques.
Formally, our model consists of a tree T with positive weights assigned to edges, and a set
R of requests that arrive in the nodes of T over time. These requests are served by subtrees
rooted at the root of T . Such a subtree X serves all requests pending at the nodes of X at cost
equal to the total weight of X. Each request incurs a waiting cost, defined by a non-negative
and non-decreasing function of time, which may be different for each request. The objective is to
minimize the sum of the total service and waiting costs. We call this the Multi-Level Aggregation
Problem (MLAP).
In most earlier papers on aggregation problems, the waiting cost function is linear, that is,
it is assumed to be simply the delay between the times when a request arrives and when it is
served. We denote this version by MLAP-L. However, most of the algorithms for this model
extend naturally to arbitrary cost functions. Another variant is MLAP-D, where each request
is given a certain deadline, has to be served before or at its deadline, and there is no penalty
associated with waiting. This can be modeled by the waiting cost function that is 0 up to the
deadline and +∞ afterwards.
In this paper, we mostly focus on the online version of MLAP, where an algorithm needs
to produce a schedule in response to requests that arrive over time. When a request appears, its
waiting cost function is also revealed. At each time t, the online algorithm needs to decide whether
to generate a service tree at this time, and if so, which nodes should be included in this tree.

3

depth 1
rand. alg. for depth 1
depth 2
fixed depth D ≥ 2
paths of arbitrary depth

MLAP and MLAP-L
upper
lower
2∗ [17]
2 [17]
∗
1.582 [20] 1.582 [31]
3 [12]
2.754 [8]
O(D4 2D ) 2.754
5∗ [9]
3.618 [9], 4

MLAP-D
upper lower
1
1
1
1
2 [8]
2 [8]
D2 2D 2
4
4

Table 1: Previous and current bounds on the competitive ratios for MLAP for trees of various
depths. Ratios written in bold are shown in this paper. Unreferenced results are either immediate
consequences of other entries in the table or trivial observations. Asterisked ratios represent
results for MLAP with arbitrary waiting cost functions, which, though not explicitly stated in the
respective papers, are straightforward extensions of the corresponding results for MLAP-L. Some
values in the table are approximations: 1.582 represents e/(e−1) and 3.618 represents 2+φ, where
φ is the golden ratio.
The main result of our paper is an O(D4 2D )-competitive algorithm for MLAP for trees of depth
D, presented in Section 5. A simpler D2 2D -competitive algorithm for MLAP-D is presented in
Section 4. No competitive algorithms have been known so far for online MLAP for arbitrary depth
trees, even for the special case of MLAP-D on trees of depth 3.
For both results we use a reduction, described in Section 3, of the general problem to the special
case of trees with fast decreasing weights described. For such trees we then provide an explicit
competitive algorithm. While our algorithm is compact and elegant, it is not a straightforward
extension of the 2-level algorithm. (In fact, we have been able to show that naı̈ve extensions of
the latter algorithm are not competitive.) It is based on carefully constructing a sufficiently large
service tree whenever it appears that an urgent request must be served. The specific structure of
the service tree is then heavily exploited in an amortization argument that constructs a mapping
from the algorithm’s cost to the cost of the optimal schedule. We believe that these three new
techniques: the reduction to trees with fast decreasing weights, the construction of the service
trees, and our charging scheme, will be useful in further studies of online aggregation problems.
In Section 6 we study a version of MLAP, that we refer to as Single-Phase MLAP (or 1P-MLAP),
in which all requests arrive at the beginning, but they also have a common expiration time that
we denote by θ. Any request not served by time θ pays waiting cost at time θ and does not need
to be served anymore. In spite of the expiration-date feature, it can be shown that 1P-MLAP
can be represented as a special case of MLAP. 1P-MLAP is a crucial tool in all the lower bound
proofs in the literature for competitive ratios of MLAP, including those in [12, 9], as well as in
our lower bounds in Section 7. It also has a natural interpretation in the context of JRP (2-level
MLAP), if we allow all orders to be canceled, say, due to changed market circumstances. In the
online variant of 1P-MLAP all requests are known at the beginning, but the expiration time θ is
unknown. For this version we give an online algorithm with competitive ratio 4, matching the
lower bound. Since 1P-MLAP can be expressed as a special case of MLAP, our result implies that
the techniques from [12, 9] cannot be used to prove a lower bound larger than 4 on the competitive
ratio for MLAP, and any study of the dependence of the competitive ratio on the depth D will
require new insights and techniques.
In Section 7 we consider MLAP on paths. For this case, we give a 4-competitive algorithm
for MLAP-D and we provide a matching lower bound. We show that the same lower bound of 4
applies to MLAP-L as well, improving the previous lower bound of 3.618 from [9].
In addition, we provide two results on offline algorithms (for arbitrary trees). In Section 8
we provide a 2-approximation algorithm for MLAP-D, significantly simpler than the LP-rounding
algorithm in [5] with the same ratio. In Section 6.3, we give a polynomial time algorithm that

4

computes optimal solutions for 1P-MLAP.
Finally, in Section 9, we discuss several technical issues concerning the use of general functions
as waiting costs in MLAP. In particular, when presenting our algorithms for MLAP we assume that
all waiting cost functions are continuous (which cannot directly capture some interesting variants
of MLAP). This is done, however, only for technical convenience; as explained in Section 9, these
algorithms can be extended to left-continuous functions, which allows to model MLAP-D as a
special case of MLAP. We also consider two alternative models for MLAP: the discrete-time model
and the model where not all requests need to be served, showing that our algorithms can be
extended to these models as well.
An extended abstract of this work appeared in the proceedings of 24th Annual European
Symposium on Algorithms (ESA’16) [6].

2

Preliminaries

Weighted trees. Let T be a tree with root r. For any set of nodes Z ⊆ T and a node x, Zx
denotes the set of all descendants of x in Z; in particular, Tx is the induced subtree of T rooted at
x. The parent of a node x is denoted parent(x). The depth of x, denoted depth(x), is the number
of edges on the simple path from r to x. In particular, r is at depth 0. The depth D of T is the
maximum depth of a node of T .
We will deal with weighted trees in this paper. For x 6= r, by `x or `(x) we denote the weight
of the edge connecting node x to its parent. For the sake of convenience, we will often refer to `x
as the weight of x. We assume that all these weights are positive. We extend this notation to r
P
by setting `r = 0. If Z is any set of nodes of T , then the weight of Z is `(Z) = x∈Z `x .
Definition of MLAP. A request ρ is specified by a triple ρ = (σρ , aρ , ωρ ), where σρ is the node of
T in which ρ is issued, aρ is the non-negative arrival time of ρ, and ωρ is the waiting cost function
of ρ. We assume that ωρ (t) = 0 for t ≤ aρ and ωρ (t) is non-decreasing for t ≥ aρ . MLAP-L is the
variant of MLAP with linear waiting costs; that is, for each request ρ we have ωρ (t) = t − aρ , for
t ≥ aρ . In MLAP-D, the variant with deadlines, we have ωρ (t) = 0 for t ≤ dρ and ωρ (t) = ∞ for
t > dρ , where dρ is called the deadline of request ρ.
In our algorithms for MLAP with general costs we will be assuming that all waiting cost
functions are continuous. This is only for technical convenience and we discuss more general
waiting cost functions in Section 9; we also show there that MLAP-D can be considered a special
case of MLAP, and that our algorithms can be extended to the discrete-time model.
A service is a pair (X, t), where X is a subtree of T rooted at r and t is the time of this
service. We will occasionally refer to X as the service tree (or just service) at time t, or even omit
t altogether if it is understood from context.
An instance J = hT , Ri of the Multi-Level Aggregation Problem (MLAP) consists of a weighted
tree T with root r and a set R of requests arriving at the nodes of T . A schedule is a set S of
services. For a request ρ, let (X, t) be the service in S with minimal t such that σρ ∈ X and t ≥ aρ .
We then say that (X, t) serves ρ and the waiting cost of ρ in S is defined as wcost(ρ, S) = ωρ (t).
Furthermore, the request ρ is called pending at all times in the interval [aρ , t]. Schedule S is called
feasible if all requests in R are served by S.
The cost of a feasible schedule S, denoted cost(S), is defined by
cost(S) = scost(S) + wcost(S),
where scost(S) is the total service cost and wcost(S) is the total waiting cost, that is
X
X
scost(S) =
`(X) and wcost(S) =
wcost(ρ, S).
ρ∈R
(X,t)∈S
The objective of MLAP is to compute a feasible schedule S for J with minimum cost(S).
5

Online algorithms. We use the standard and natural definition of online algorithms and the
competitive ratio. We assume the continuous time model. The computation starts at time 0 and
from then on the time gradually progresses. At any time t new requests can arrive. If the current
time is t, the algorithm has complete information about the requests that arrived up until time
t, but has no information about any requests whose arrival times are after time t. The instance
includes a time horizon H that is not known to the online algorithm, which is revealed only at
time t = H. At time H, all requests that are still pending must be served. (In the offline case, H
can be assumed to be equal to the maximum request arrival time.)
If A is an online algorithm and R ≥ 1, we say that A is R-competitive 1 if cost(S) ≤ R · opt(J )
for any instance J of MLAP, where S is the schedule computed by A on J and opt(J ) is the
optimum cost for J .
Quasi-root assumption. Throughout the paper we will assume that r, the root of T , has only
one child. This is without loss of generality, because if we have an algorithm (online or offline)
for MLAP on such trees, we can apply it independently to each child of r and its subtree. This
will give us an algorithm for MLAP on arbitrary trees with the same performance. From now on,
let us call the single child of r the quasi-root of T and denote it by q. Note that q is included in
every (non-trivial) service.
Urgency functions. When choosing nodes for inclusion in a service, our online algorithms
give priority to those that are most “urgent”. For MLAP-D, naturally, urgency of nodes can be
measured by their deadlines, where a deadline of a node v is the earliest deadline of a request
pending in the subtree Tv , i.e., the induced subtree rooted at v. But for the arbitrary instances of
MLAP we need a more general definition of urgency, which takes into account the rate of increase
of the waiting cost in the future. To this end, each of our algorithms will use some urgency function
f : T → R ∪ {+∞}, which also depends on the set of pending requests and the current time step,
and which assigns some time value to each node. The earlier this value, the more urgent the node
is.
Fix some urgency function f . Then, for any set A of nodes in T and a real number β, let
Urgent(A, β, f ) be the set of nodes obtained by choosing the nodes from A in order of their increasing urgency value, until either their total weight exceeds β or we run out of nodes. More precisely,
we define Urgent(A, β, f ) as the smallest set of nodes in A such that (i) for all u ∈ Urgent(A, β, f ),
and v ∈ A − Urgent(A, β, f ) we have f (u) ≤ f (v), and (ii) either `(Urgent(A, β, f )) ≥ β or
Urgent(A, β, f ) = A. In case of ties in the values of f there may be multiple choices for A; we
choose among them arbitrarily.

3

Reduction to L-Decreasing Trees

One basic intuition that emerges from earlier works on trees of depth 2 (see [12, 11, 8]) is that
the hardest case of the problem is when `q , the weight of the quasi-root, is much larger than the
weights of leaves. For arbitrary depth trees, the hard case is when the weights of nodes quickly
decrease with their depth. We show that this is indeed the case, by defining the notion of Ldecreasing trees that captures this intuition and showing that MLAP reduces to the special case
of MLAP for such L-decreasing trees, increasing the competitive ratio by a factor of at most DL.
This is a general result, not limited only to algorithms in our paper.
Formally, for L ≥ 1, we say that T is L-decreasing if for each node u 6= r and each child v of
u we have `u ≥ L · `v . (The value of L used in our algorithms will be fixed later.)
1 Definitions

of competitiveness in the literature often allow an additive error term, independent of the request
sequence. For our algorithms, this additive term is not needed. Our lower bound proofs can be easily modified
(essentially, by iterating the adversary strategy) to remain valid if an additive term is allowed, even if it is a function
of T .

6

Note that the L-decreasing condition corresponds to the usual definition of hierarchically wellseparated trees (HSTs); however, for our purposes we do not need any balancing condition usually
also required from HSTs.
Theorem 3.1. Assume that there exists an R-competitive algorithm A for MLAP (resp. MLAP-D)
on L-decreasing trees (where R can be a function of D, the tree depth). Then there exists a (DLR)competitive algorithm B for MLAP (resp. MLAP-D) on arbitrary trees.
Proof. Fix the underlying instance J = (T , R), where T is a tree and R is a sequence of requests
in T . In our reduction, we convert T to an L-decreasing tree T 0 on the same set of nodes. We
then show that any service on T is also a service on T 0 of the same cost and, conversely, that any
service on T 0 can be converted to a slightly more expensive service on T .
We start by constructing an L-decreasing tree T 0 on the same set of nodes. For any node
u ∈ T − {r}, the parent of u in T 0 will be the lowest (closest to u) ancestor w of u in T such
that `w ≥ L · `u ; if no such w exists, we take w = r. Note that T 0 may violate the quasi-root
assumption, which does not change the validity of the reduction, as we may use independent
instances of the algorithm for each child of r in T 0 . Since in T 0 each node u is connected to one
of its ancestors from T , it follows that T 0 is a tree rooted at r with depth at most D. Obviously,
T 0 is L-decreasing.
The construction implies that if a set of nodes X is a service subtree of T , then it is also a
service subtree for T 0 . (However, note that the actual topology of the trees with node set X in
T and T 0 may be very different. For example, if L = 5 and T is a path with costs (starting from
the leaf) 1, 2, 22 , ..., 2D , then in T 0 the node of weight 2i is connected to the node of weight 2i+3 ,
except for the last three nodes that are connected to r. Thus the resulting tree consists of three
paths ending at r with roughly the same number of nodes.) Therefore, any schedule for J is also
a schedule for J 0 = (T 0 , R), which gives us that opt(J 0 ) ≤ opt(J ).
The algorithm B for T is defined as follows: On a request sequence R, we simulate A for R in
T 0 , and whenever A contains a service X, B issues the service X 0 ⊇ X, created from X as follows:
Start with X 0 = X. Then, for each u ∈ X − {r}, if w is the parent of u in T 0 , then add to X 0 all
inner nodes on the path from u to w in T . By the construction of T 0 , for each u we add at most
D −1 nodes, each of weight less than L·`u . It follows that `(X 0 ) ≤ ((D −1)L+1)`(X) ≤ DL·`(X).
In total, the service cost of B is at most DL times the service cost of A. Any request served
by A is served by B at the same time or earlier, thus the waiting cost of B is at most the waiting
cost of A (resp. for MLAP-D, B produces a valid schedule for J ). Since A is R-competitive, we
obtain
cost(B, J ) ≤ DL · cost(A, J 0 ) ≤ DLR · opt(J 0 ) ≤ DLR · opt(J ),
and thus B is DLR-competitive.

4

A Competitive Algorithm for MLAP-D

In this section we present our online algorithm for MLAP-D with competitive ratio at most D2 2D .
To this end, we will give an online algorithm that achieves competitive ratio RL = (2 + 1/L)D−1
for L-decreasing trees. Taking L = D/2 and using the reduction to L-decreasing trees from
Theorem 3.1, we obtain a D2 2D -competitive algorithm for arbitrary trees.

4.1

Intuitions

Consider the optimal 2-competitive algorithm for MLAP-D for trees of depth 2 [8]. Assume that
the tree is L-decreasing, for some large L. (Thus `q  `v , for each leaf v.) Whenever a pending
request reaches its deadline, this algorithm serves a subtree X consisting of r, q and the set of
leaves with the earliest deadlines and total weight of about `q . This is a natural strategy: We have

7

to pay at least `q to serve the expiring request, so including an additional set of leaves of total
weight `q can at most double our overall cost. But, assuming that no new requests arrive, serving
this X can significantly reduce the cost in the future, since servicing these leaves individually is
expensive: it would cost `v + `q per each leaf v, compared to the incremental cost of `v to include
v in X.
For L-decreasing trees with three levels (that is, for D = 3), we may try to iterate this idea.
When constructing a service tree X, we start by adding to X the set of most urgent children of q
whose total weight is roughly `q . Now, when choosing nodes of depth 3, we have two possibilities:
(1) for each v ∈ X − {r, q} we can add to X its most urgent children of combined weight `v (note
that their total weight will add up to roughly `q , because of the L-decreasing property), or (2)
from the set of all children of the nodes in X − {r, q}, add to X the set of total weight roughly `q
consisting of (globally) most urgent children.
It is not hard to show that option (1) does not lead to a constant-competitive algorithm: The
counter-example involves an instance with one node w of depth 2 having many children with
requests with early deadlines and all other leaves having requests with very distant deadlines.
Assume that `q = L2 , `w = L, and that each leaf has weight 1. The example forces the algorithm
to serve the children of w in small batches of size L with cost more than L2 per batch or L per each
child of w, while the optimum can serve all the requests in the children of w at once with cost O(1)
per request, giving a lower bound Ω(L) on the competitive ratio. (The requests at other nodes
can be ignored in the optimal solution, as we can keep repeating the above strategy in a manner
similar to the lower-bound technique for 1P-MLAP that will be described in Section 6. Reissuing
requests at the nodes other than w will not increase the cost of the optimum.) A more intricate
example shows that option (2) by itself is not sufficient to guarantee constant competitiveness
either.
The idea behind our algorithm, for trees of depth D = 3, is to do both (1) and (2) to obtain X.
This increases the cost of each service by a constant factor, but it protects the algorithm against
both bad instances. The extension of our algorithm to depths D > 3 carefully iterates the process
of constructing the service tree X, to ensure that for each node v ∈ X and for each level i below
v we add to X sufficiently many urgent descendants of v at that level.

4.2

Notations

To give a formal description, we need some more notations. For any set of nodes Z ⊆ T , let Z i
denote the set of nodes in Z of depth i in tree T . (Recall that r has depth 0, q has depth 1, and
Si−1
leaves have depth at most D.) Let also Z <i = j=0 Z j and Z ≤i = Z <i ∪ Z i . These notations can
be combined with the notation Zx , so, e.g., Zx<i is the set of all descendants of x that belong to
Z and whose depth in T is smaller than i.
We assume that all the deadlines in the given instance are distinct. This may be done without
loss of generality, as in case of ties we can modify the deadlines by infinitesimally small perturbations and obtain an algorithm for the general case.
At any given time t during the computation of the algorithm, for each node v, let dt (v) denote
the earliest deadline among all requests in Tv (i.e., among all descendants of v) that are pending
for the algorithm; if there is no pending request in Tv , we set dt (v) = +∞. We will use the function
dt as the urgency (see Section 2) of nodes at time t, i.e., a node u will be considered more urgent
than a node v if dt (u) < dt (v).

4.3

Algorithm OnlTreeD

At any time t when some request expires, that is when t = dt (r), the algorithm serves a subtree
X constructed by first initializing X = {r, q}, and then incrementally augmenting X according to
the following pseudo-code:

8

for each depth i = 2, . . . , D
Z i ← set of all children of nodes in X i−1
for each v ∈ X <i
U (v, i, t) ← Urgent(Zvi , `v , dt )
X ← X ∪ U (v, i, t)
In other words, at depth i, we restrict our attention to Z i , the children of all the nodes in
X i−1 , i.e., of the nodes that we have previously selected to X at level i − 1. (We start with i = 2
and X 1 = {q}.) Then we iterate over all v ∈ X <i and we add to X the set U (v, i, t) of nodes from
Tvi (descendants of v at depth i) whose parents are in X, one by one, in the order of increasing
deadlines, stopping when either their total weight exceeds `v or when we run out of such nodes.
Note that these sets do not need to be disjoint.
The constructed set X is a service tree, as we are adding to it only nodes that are children of
the nodes already in X.
Let ρ be the request triggering the service at time t, i.e., satisfying dρ = t. (By the assumption
about different deadlines, ρ is unique.) Naturally, all the nodes u on the path from r to σρ have
dt (u) = t and qualify as the most urgent, thus the node σρ is included in X. Therefore every
request is served before its deadline.

4.4

Analysis

Intuitively, it should be clear that Algorithm OnlTreeD cannot have a better competitive ratio
than `(X)/`q : If all requests are in q, the optimum will serve only q, while our algorithm uses a
set X with many nodes that turn out to be useless. As we will show, via an iterative charging
argument, the ratio `(X)/`q is actually achieved by the algorithm.
Recall that RL = (2 + 1/L)D−1 . We now prove a bound on the cost of the service tree.
Lemma 4.1. Let X be the service tree produced by Algorithm OnlTreeD at time t. Then
`(X) ≤ RL · `q .
Proof. We prove by induction that `(X ≤i ) ≤ (2 + 1/L)i−1 `q for all i ≤ D.
The base case of i = 1 is trivial, as X ≤1 = {r, q} and `r = 0. For i ≥ 2, X i is the union of
the sets U (v, i, t) over all nodes v ∈ X <i . Since T is L-decreasing, each node in the set U (v, i, t)
has weight at most `v /L. Thus the total weight of U (v, i, t) is at most `(U (v, i, t)) ≤ `v + `v /L =
(1 + 1/L)`v . Therefore, by the inductive assumption, we get that
`(X ≤i ) ≤ (1 + (1 + 1/L)) · `(X <i )
≤ (2 + 1/L) · (2 + 1/L)i−2 `q = (2 + 1/L)i−1 `q ,
proving the induction step and completing the proof that `(X) ≤ RL · `q .
The competitive analysis uses a charging scheme. Fix some optimal schedule S∗ . Consider
a service (X, t) of Algorithm OnlTreeD. We will identify in X a subset of “critically overdue”
nodes (to be defined shortly) of total weight at least `q ≥ `(X)/RL , and we will show that for each
such critically overdue node v we can charge the portion `v of the service cost of X to an earlier
service in S∗ that contains v. Further, any node in service of S∗ will be charged at most once.
This implies that the total cost of our algorithm is at most RL times the optimal cost, giving us
an upper bound of RL on the competitive ratio for L-decreasing trees.
In the proof, by nostv we denote the time of the first service in S∗ that includes v and is strictly
after time t; we also let nostv = +∞ if no such service exists (nos stands for next optimal service).
For a service (X, t) of the algorithm, we say that a node v ∈ X is overdue at time t if dt (v) < nostv .
Servicing of such v is delayed in comparison to S∗ , because S∗ must have served v before or at
time t. Note also that r and q are overdue at time t, as dt (r) = dt (q) = t by the choice of the
9

σρ

w
r

q

Y

v
x

U(v,i,t)

X

i
Figure 1: Illustration of the proof of Lemma 4.2.

service time. We define v ∈ X to be critically overdue at time t if (i) v is overdue at t, and (ii)
there is no other service of the algorithm in the time interval (t, nostv ) in which v is overdue.
We are now ready to define the charging for a service (X, t). For each v ∈ X that is critically
overdue, we charge its weight `v to the last service of v in S∗ before or at time t. This charging is
well-defined as, for each overdue v, there must exist a previous service of v in S∗ . The charging is
obviously one-to-one because between any two services in S∗ that involve v there may be at most
one service of the algorithm in which v is critically overdue. The following lemma shows that the
total charge from X is large enough.
Lemma 4.2. Let (X, t) be a service of Algorithm OnlTreeD and suppose that v ∈ X is overdue
at time t. Then the total weight of critically overdue nodes in Xv at time t is at least `v .
Proof. The proof is by induction on the depth of Tv , the induced subtree rooted at v.
The base case is when Tv has depth 0, that is when v is a leaf. We show that in this case
v must be critically overdue, which implies the conclusion of the lemma. Towards contradiction,
suppose that there is some other service at time t0 ∈ (t, nostv ) in which v is overdue. Since v is a
leaf, after the service at time t there are no pending requests in Tv = {v}. This would imply that
there is a request ρ with σρ = v such that t < aρ ≤ dρ < nostv . But this is not possible, because
S∗ does not serve v in the time interval (t, nostv ). Thus v is critically overdue and the base case
holds.
Assume now that v is not a leaf, and that the lemma holds for all descendants of v. If v is
critically overdue, the conclusion of the lemma holds.
Thus we can now assume that v is not critically overdue. This means that there is a service
(Y, t0 ) of Algorithm OnlTreeD with t < t0 < nostv which contains v and such that v is overdue
0
at t0 . Thus nostv = nostv .
0
Let ρ be the request with dρ = dt (v), i.e., the most urgent request in Tv at time t0 .
We claim that aρ ≤ t, i.e., ρ arrived no later than at time t. Indeed, since v is overdue at time
0
t0 , it follows that dρ < nostv = nostv . The optimal schedule S∗ cannot serve ρ after time t, as S∗
has no service from v in the interval (t, dρ ]. Thus S∗ must have served ρ before or at t, and hence
aρ ≤ t, as claimed.
Now consider the path from σρ to v in Y . (See Figure 1.) As ρ is pending for the algorithm at
time t and ρ is not served by (X, t), it follows that σρ 6∈ X. Let w be the last node on this path
in Y − X. Then w is well-defined and w 6= v, as v ∈ X. Let i be the depth of w. Note that the
parent of w is in Xv<i , so w ∈ Z i in the algorithm when X is constructed.

10

The node σρ is in Tw and ρ is pending at t, thus we have dt (w) ≤ dρ . Since w ∈ Z i but w
was not added to X at time t, we have that `(U (v, i, t)) ≥ `v and each x ∈ U (v, i, t) is at least as
urgent as w. This implies that such x satisfies
0

dt (x) ≤ dt (w) ≤ dρ < nostv = nostv ≤ nostx ,
thus x is overdue at time t. By the inductive assumption, the total weight of critically overdue
nodes in each induced subtree Xx is at least `x . Adding these weights over all x ∈ U (v, i, t),
we obtain that the total weight of critically overdue nodes in Xv is at least `(U (v, i, t)) ≥ `v ,
completing the proof.
Now consider a service (X, t) of the algorithm. The quasi-root q is overdue at time t, so
Lemmata 4.2 and 4.1 imply that the charge from (X, t) is at least `q ≥ `(X)/RL . Since each
node in any service in S∗ is charged at most once, we conclude that Algorithm OnlTreeD is
RL -competitive for any L-decreasing tree T .
From the previous paragraph, using Theorem 3.1, we now obtain that there exists a DLRL =
DL(2 + 1/L)D−1 -competitive algorithm for general trees. For D ≥ 2, choosing L = D/2 yields a
competitive ratio bounded by 21 D2 2D−1 · (1 + 1/D)D ≤ 41 D2 2D · e ≤ D2 2D . (For D = 1 there is a
trivial 1-competitive algorithm for MLAP-D.) Summarizing, we obtain the following result.
Theorem 4.3. There exists a D2 2D -competitive online algorithm for MLAP-D.

5

A Competitive Algorithm for MLAP

In this section we show that there is an online algorithm for MLAP whose competitive ratio for
trees of depth D is O(D4 2D ). As in Section 4, we will assume that the tree T in the instance
is L-decreasing. Then, for L-decreasing trees, we will present a competitive algorithm, which
will imply the existence of a competitive algorithm for arbitrary trees by using Theorem 3.1 and
choosing an appropriate value of L.

5.1

Preliminaries and Notations

Recall that ωρ (t) denotes the waiting cost function of a request ρ. As explained in Section 2, we
assume that the waiting cost functions are continuous. (In Section 9 we discuss how to extend our
results to arbitrary waiting cost functions.) We will overload this notation, so that we can talk
about the waiting cost of a set of requests or a set of nodes. Specifically, for a set P of requests
and a set Z of nodes, let
X
ωP (Z, t) =
ωρ (t).
ρ∈P :σρ ∈Z

Thus ωP (Z, t) is the total waiting cost of the requests from P that are issued in Z. We sometimes
omit P , in which case the notation refers to the set of all requests in the instance, that is ω(Z, t) =
ωR (Z, t). Similarly, we omit Z when Z contains all nodes, that is ωP (t) = ωP (T , t).
Maturity time. In our algorithm for MLAP-D in Section 4, the times of services and the urgency
of nodes are both naturally determined by the deadlines. For MLAP with continuous waiting costs
there are no hard deadlines. Nevertheless, we can still introduce the notion of maturity time of a
node, which is, roughly speaking, the time when some subtree rooted at this node has its waiting
cost equal to its service cost; this subtree is then called mature. This maturity time will be our
urgency function, as discussed earlier in Section 2. We use the maturity time in two ways: one,
the maturity times of the quasi-root determine the service times, and two, maturity times of other
nodes are used to prioritize them for inclusion in the service trees. We now proceed to define these
notions.
11

Consider some time t and any set P ⊆ R of requests. A subtree Z of T (not necessarily rooted
at r) is called P -mature at time t if ωP (Z, t) ≥ `(Z). Also, let µP (Z) denote the minimal time τ
such that ωP (Z, τ ) = `(Z); we let µP (Z) = ∞ if such τ does not exist. In other words, µP (Z) is
the earliest τ at which Z is P -mature. Since ωP (Z, 0) = 0 and ωP (Z, t) is a non-decreasing and
continuous function of t, µP (Z) is well-defined.
For a node v, let the P -maturity time of v, denoted MP (v), be the minimum of values µP (Z)
over all subtrees Z of T rooted at v. The tree Z that achieves this minimum will be denoted CP (v)
and called the P -critical subtree rooted at v; if there are more such trees, choose one arbitrarily.
Therefore we have ωP (CP (v), MP (v)) = `(CP (v)).
The following simple lemma guarantees that the maturity time of any node in the P -critical
subtree CP (v) is upper bounded by the maturity time of v.
Lemma 5.1. Let u ∈ CP (v) and let Y = (CP (v))u be the induced subtree of CP (v) rooted at u.
Then MP (u) ≤ µP (Y ) ≤ MP (v).
Proof. The first inequality follows directly from the definition of MP (u). To show the second
inequality, we proceed by contradiction. Let t = MP (v). If the second inequality does not hold,
then u 6= v and ωP (Y, t) < `(Y ). Take Y 0 = CP (v) − Y , which is a tree rooted at v. Since
ωP (CP (v), t) = `(CP (v)), we have that ωP (Y 0 , t) = ωP (CP (v), t) − ωP (Y, t) > `(CP (v)) − `(Y ) =
`(Y 0 ). This in turn implies that µP (Y 0 ) < t, which is a contradiction with the definition of
t = MP (v).
Most of the references to maturity of a node or to its critical set will be made with respect to
the set of requests pending for our algorithm at a given time. For any time t, we will use notation
M t (v) and C t (v) to denote the time MP (v) and the P -critical subtree CP (v), where P is the set
of requests pending for the algorithm at time t; if the algorithm schedules a service at some time
t, P is the set of requests that are pending at time t right before the service is executed. Note
that in general it is possible that M t (v) < t. However, our algorithm will maintain the invariant
that for the quasi-root q we will have M t (q) ≥ t at each time t.

5.2

Algorithm

We now describe our algorithm for L-decreasing trees. A service will occur at each maturity
time of the quasi-root q (with respect to the pending requests), that is at each time t for which
t = M t (q). At such a time, the algorithm chooses a service that contains the critical subtree
C = C t (q) of q and an extra set E, whose service cost is not much more expensive than that of C.
The extra set is constructed similarly as in Algorithm OnlTreeD, where the urgency of nodes is
now measured by their maturity time. In other words, our urgency function is now f = M t (see
Section 2.) As before, this extra set will be a union of a system of sets U (v, i, t) for i = 2, . . . , D,
and v ∈ C <i ∪ E <i , except that now, for technical reasons, the sets U (v, i, t) will be mutually
disjoint and also disjoint from C.
Algorithm OnlTree. At any time t such that t = M t (q), serve the set X = C ∪ E constructed
according to the following pseudo-code:
C ← C t (q) ∪ {r}
E←∅
for each depth i = 2, . . . , D
Z i ← set of all nodes in T i − C whose parent is in C ∪ E
for each v ∈ (C ∪ E)<i
U (v, i, t) ← Urgent(Zvi , `v , M t )
E ← E ∪ U (v, i, t)
Z i ← Z i − U (v, i, t)
12

At the end of the instance (when t = H, the time horizon), if there are any pending requests, issue
the last service that contains all nodes v with a pending request in Tv .
Note that X = C ∪ E is indeed a service tree, as it contains r, q and we are adding to it only
nodes that are children of the nodes already in X. The initial choice and further changes of Z i
imply that the sets U (v, i, t) are pairwise disjoint and disjoint from C – a fact that will be useful
in our analysis.
We also need the following fact.
Lemma 5.2. (a) Suppose that Algorithm OnlTree issues a service at a time t, that is M t (q) = t.
+
+
Denote by M t (q) the maturity time of q right after the service at time t. Then M t (q) > t. (b)
At any time t we have M t (q) ≥ t.
+

To clarify the meaning of “right after the service” in this lemma, M t (q) is defined formally
as the limit of M τ (q), with τ approaching t from the right.
Proof. (a) Let M t (q) = t and let (X, t) be the service at time t. This means that we have
ω(X, t) = `(X) and ω(Y, t) ≤ `(Y ) for all subtrees Y of T rooted at r. Consider any subtree Y
of T rooted at r different from X. Denoting by ω(Y, t+ ) the waiting cost of the packets that are
pending in Y right after the service (X, t), it is sufficient to prove that ω(Y, t+ ) < `(Y ).
Towards contradiction, suppose that ω(Y, t+ ) ≥ `(Y ). Then we have
ω(X ∪ Y, t) = ω(X, t) + ω(Y − X, t)
= ω(X, t) + ω(Y, t+ )
≥ `(X) + `(Y )
> `(X ∪ Y ),
where the last (strict) inequality follows from q ∈ X ∩ Y and `q > 0. But X ∪ Y is a subtree of T
rooted at r, so the inequality ω(X ∪ Y, t) > `(X ∪ Y ) contradicts our assumption that M t (q) = t.
(b) The lemma holds trivially at the beginning, at time t = 0. In any time interval without
new requests released nor services, the inequality M t (q) ≥ t is preserved, by the definition of the
service times and continuity of waiting cost functions. Releasing a request ρ at a time aρ = t
cannot decrease M t (q) to below t, because the waiting cost function of ρ is identically 0 up to t
and thus releasing ρ does not change the waiting costs at time t or before. Finally, part (a) implies
that the inequality is also preserved when services are issued.
By Lemma 5.2 (and the paragraph before), the definition of the algorithm is sound, that is the
sequence of service times is non-decreasing. In fact, the lemma shows that no two services can
occur at the same time.

5.3

Competitive Analysis

We now present the proof of the existence of an O(D4 2D )-competitive algorithm for MLAP for
trees of depth D. The overall argument is quite intricate, so we will start by summarizing its main
steps:
• First, as explained earlier, we will assume that the tree T in the instance is L-decreasing.
For such T we will show that Algorithm OnlTree has competitive ratio O(D2 RL ), where
RL = (2 + 1/L)D−1 . Our bound on the competitive ratio for arbitrary trees will then follow,
by using Theorem 3.1 and choosing an appropriate value of L (see Theorem 5.8).
• For L-decreasing trees, the bound of the competitive ratio of Algorithm OnlTree involves
four ingredients:

13

– We show (in Lemma 5.3) that the total cost of Algorithm OnlTree is at most twice
its service cost.
– Next, we show that the service cost of Algorithm OnlTree can be bounded (within a
constant factor) by the total cost of all critical subtrees C t (q) of the service trees in its
schedule.
– To facilitate the estimate of the adversary cost, we introduce the concept of a pseudoschedule denoted S. The pseudo-schedule S is a collection of pseudo-services, which
include the services from the original adversary schedule S∗ . We show (in Lemma 5.5)
that the adversary pseudo-schedule has service cost not larger than D times the cost of
S∗ . Using the pseudo-schedule allows us to ignore the waiting cost in the adversary’s
schedule.
– With the above bounds established, it remains to show that the total cost of critical
subtrees in the schedule of Algorithm OnlTree is within a constant factor of the
service cost of the adversary’s pseudo-schedule. This is accomplished through a charging
scheme that charges nodes (or, more precisely, their weights) from each critical subtree
of Algorithm OnlTree to their appearances in some earlier adversary pseudo-services.
Two auxiliary bounds. We now assume that T is L-decreasing and proceed with our proof,
according to the outline above.
The definition of the maturity time implies that the waiting cost of all the requests served is
at most the service cost `(X), as otherwise X would be a good candidate for a critical subtree at
some earlier time. Denoting by S the schedule computed by Algorithm OnlTree, we thus obtain:
Lemma 5.3. cost(S) ≤ 2 · scost(S).
Using Lemma 5.3, we can restrict ourselves to bounding the service cost, losing at most a factor
of 2. We now bound the cost of a given service X; recall that RL = (2 + 1/L)D−1 .
Lemma 5.4. Each service tree X = C ∪E constructed by the algorithm satisfies `(X) ≤ RL ·`(C).
Proof. Since T is L-decreasing, the weight of each node that is a descendant of v is at most `v /L
and thus `(U (v, i, t)) ≤ (1 + 1/L)`v .
We now estimate `(X). We claim and prove by induction for i = 1, . . . , D that
`(X ≤i ) ≤ (2 + 1/L)i−1 `(C ≤i ) .

(1)

The base case for i = 1 is trivial, as X ≤1 = C ≤1 = {r, q}. For i ≥ 2, the set X i consists of C i
and the sets U (v, i, t), for v ∈ X <i . Each of these sets U (v, i, t) has weight at most (1 + 1/L)`v .
Therefore
`(X i ) ≤ (1 + 1/L)`(X <i ) + `(C i ) .
(2)
Now, using (2) and the inductive assumption (1) for i − 1, we get
`(X ≤i ) = `(X <i ) + `(X i )
≤ (2 + 1/L)`(X <i ) + `(C i )
≤ (2 + 1/L)i−1 `(C <i ) + `(C i ) ≤ (2 + 1/L)i−1 `(C ≤i ).
Taking i = D in (1), the lemma follows.

14

Waiting costs and pseudo-schedules. Our plan is to charge the cost of Algorithm OnlTree
to the optimal (or the adversary’s) cost. Let S∗ be an optimal schedule. To simplify this charging,
we extend S∗ by adding to it pseudo-services, where a pseudo-service from a node v is a partial
service of cost `v that consists only of the edge from v to its parent. We denote this modified
schedule S and call it a pseudo-schedule, reflecting the fact that its pseudo-services are not necessarily subtrees of T rooted at r. Adding such pseudo-services will allow us to ignore the waiting
costs in the optimal schedule.
We now define more precisely how to obtain S from S∗ . For each node v independently we define
the times when new pseudo-services of v occur in S. Intuitively, we introduce these pseudo-services
at intervals such that the waiting cost of the requests that arrive in Tv during these intervals adds
up to `v . The formal description of this process is given in the pseudo-code below, where we use
notation R(> t) for the set of requests ρ ∈ R with aρ > t (i.e., requests issued after time t). Recall
that H denotes the time horizon.
t ← −∞
while ωR(>t) (Tv , H) ≥ `v
let τ be the earliest time such that ωR(>t) (Tv , τ ) = `v
add to S a pseudo-service of v at τ
t←τ
We apply the above procedure to all the nodes v ∈ T − {r} such that R contains a request in
Tv . The new pseudo-schedule S contains all the services of S∗ (treated as sets of pseudo-services
of all served nodes) and the new pseudo-services added as above. The service cost of the pseudoschedule, scost(S), is defined naturally as the total weight of the nodes in all its pseudo-services.
Lemma 5.5. scost(S) ≤ D · cost(S∗ ).
Proof. It is sufficient to show that the total service cost of the new pseudo-services added inside
the while loop is at most scost(S∗ ) + D · wcost(S∗ ): Adding scost(S∗ ) once more to account for the
service cost of the services of S∗ that are included in S, and using our assumption that D ≥ 3, we
obtain scost(S) ≤ 2 · scost(S∗ ) + D · wcost(S∗ ) ≤ D · cost(S∗ ), thus the lemma follows.
To prove the claim, consider some node v, and a pair of times t, τ from one iteration of the
while loop, when a new pseudo-service was added to S at time τ . This pseudo-service has cost
`v . In S∗ , either there is a service in (t, τ ] including v, or the total waiting cost of the requests
within Tv released in this interval is equal to ωR(>t) (Tv , τ ) = `v . In the first case, we charge the
cost of `v of this pseudo-service to any service of v in S∗ in (t, τ ]. Since we consider here only the
new pseudo-services, created by the above pseudo-code, this charging will be one-to-one. In the
second case, we charge `v to the total waiting cost of the requests in Tv released in the interval
(t, τ ]. For each given v, the charges of the second type from pseudo-services at v go to disjoint
sets of requests in Tv , so each request in Tv will receive at most one charge from v. Therefore,
for each request ρ, its waiting cost in S∗ will be charged at most D times, namely at most once
from each node v on the path from σρ to q. From the above argument, the total cost of the new
pseudo-services is at most scost(S∗ ) + D · wcost(S∗ ), as claimed.
Using the bound in Lemma 5.5 will allow us to use scost(S) as an estimate of the optimal cost
in our charging scheme, losing at most a factor of D in the competitive ratio.
Charging scheme. According to Lemma 5.3, to establish constant competitiveness it is sufficient to bound only the service cost of Algorithm OnlTree. By Lemma 5.4 for any service tree
X of the algorithm we have `(X) ≤ RL · `(C). Therefore, it is in fact sufficient to bound the
total weight of the critical sets in the algorithm’s services. Further, using Lemma 5.5, instead of
using the optimal cost in this bound, we can use the pseudo-service cost. Following this idea, we

15

will show how we can charge, at a constant rate, the cost of all critical sets C in the algorithm’s
services to the adversary pseudo-services.
The basic idea of our charging method is similar to that for MLAP-D. The argument in Section 4
can be interpreted as an iterative charging scheme, where we have a charge of `q that originates
from q, and this charge is gradually distributed and transferred down the service tree, through
overdue nodes, until it reaches critically overdue nodes that can be charged directly to adversary
services. For MLAP with general waiting costs, the charge of `(C) will originate from the current
critical subtree C. Several complications arise when we attempt to distribute the charges to nodes
at deeper levels. First, due to gradual accumulation of waiting costs, it does not seem possible to
identify nodes in the same service tree that can be used as either intermediate or final nodes in this
process. Instead, when defining a charge from a node v, we will charge descendants of v in earlier
services of v. Specifically, the weight `v will be charged to the set U (v, i, t− ) for some i > depth(v),
where t− is the time of the previous service of the algorithm that includes v. The nodes — or,
more precisely, services of these nodes — that can be used as intermediate nodes for transferring
charges will be called depth-timely. As before, we will argue that each charge will eventually reach
a node u in some earlier service that can be charged to some adversary pseudo-service directly.
Such service of u will be called u-local, where the name reflects the property that this service has
an adversary pseudo-service of u nearby (to which its weight `u will be charged).
We now formalize these notions. Let (X, t) be some service of Algorithm OnlTree that
includes v, that is v ∈ X. By Prevt (v) we denote the time of the last service of v before t in the
schedule of the algorithm; if it does not exist, set Prevt (v) = −∞. By Nextt (v, i) we denote the
time of the ith service of v following t in the schedule of the algorithm; if it does not exist, set
Nextt (v, i) = +∞.
We say that the service of v at time t < H is i-timely, if M t (v) < Nextt (v, i); furthermore,
if v is depth(v)-timely, we will say simply that this service of v is depth-timely. We say that the
service of v at time t < H is v-local, if this is either the first service of v by the algorithm, or if
there is an adversary pseudo-service of v in the interval (Prevt (v), Nextt (v, depth(v))].
Given an algorithm’s service (X, t), we now define the outgoing charges from X. For any
v ∈ X − {r}, its outgoing charge is defined as follows:
(C1) If t < H and the service of v at time t is both depth-timely and v-local, charge `v to the
first adversary pseudo-service of v after time Prevt (v).
(C2) If t < H and the service of v at time t is depth-timely but not v-local, charge `v to the
algorithm’s service at time Prevt (v).
(C3) If t < H and the service of v at time t is not depth-timely, the outgoing charge is 0.
(C4) If t = H and v ∈ X, we charge `v to the first adversary pseudo-service of v.
We first argue that the charging is well-defined. To justify (C1) suppose that this service is
depth-timely and v-local. If (X, t) is the first service of v then Prevt (v) = −∞ and the charge goes
to the first pseudo-service of v which exists as all the requests must be served. Otherwise there
is an adversary pseudo-service of v in the interval (Prevt (v), Nextt (v, depth(v))] and rule (C1) is
well-defined. For (C2), note that if the service (X, t) of v is not v-local then there must be an
earlier service including v. (C3) is trivial. For (C4), note again that an adversary transmission of
v must exist, as all requests must be served.
The following lemma implies that all nodes in the critical subtree will have an outgoing charge,
as needed.
Lemma 5.6. For a transmission time t < H, each v ∈ C t (q) is 1-timely, and thus also depthtimely.

16

Proof. From Lemma 5.1, each v ∈ C t (q) satisfies M t (v) ≤ M t (q) = t < Nextt (q, 1) ≤ Nextt (v, 1),
where the sharp inequality follows from Lemma 5.2.
The following lemma captures the key property of our charging scheme. For any depth-timely
service of v ∈ X that is not v-local, it identifies a set U (v, i, t− ) in the previous service (X − , t− )
including v that is suitable for receiving a charge. It is important that each such set is used
only once, has sufficient weight, and contains only depth-timely nodes. As we show later, these
properties imply that in this charging scheme the net charge (the difference between the outgoing
and incoming charge) from each service X is at least as large as the total weight of its critical
subtree.
As in the argument for MLAP-D, we need to find an urgent node w ∈ Xv which is not in X −
and has its parent in X − . There are two important issues caused by the fact that the urgency
is given by the maturity times instead of deadlines. The first issue is that the maturity time
can decrease due to new packet arrivals — to handle this, we argue that if the new requests had
large waiting costs, they would guarantee the existence of a pseudo-service of node v in the given
time interval and thus the algorithm’s service of v would be v-local. The second issue is that
the maturity time is not given by a single descendant but by adding the node contributions from
the whole tree — thus instead of searching for w on a single path, we need a more subtle, global
argument to identify such w.
Lemma 5.7. Assume that the service of v at time t < H is depth-timely and not v-local. Let
i = depth(v), and let (X − , t− ) be the previous service of Algorithm OnlTree including v, that
is t− = Prevt (v). Then there exists j > i such that all the nodes in the set U (v, j, t− ) from the
construction of X − in the algorithm are depth-timely and `(U (v, j, t− )) ≥ `v .
Proof. Let t∗ = M t (v) and let C 0 = C t (v) be the critical subtree of v at time t. Since the service
of v at time t is i-timely, we have t∗ < Nextt (v, i). (It may be the case that t∗ < t, but that does
not hamper our proof in any way.) Also, since the service of v at time t is not v-local, it is not
the first service of v, thus t− and X − are defined.
Let P − be the set of requests pending right after time t− (including those with arrival time t−
but not those served at time t− ), and let P be the set of requests with arrival time in the interval
(t− , t]. The key observation is that the total waiting cost of all the requests in C 0 that arrived
after t− satisfies
ωP (C 0 , t∗ ) < `v .
(3)
To see this, simply note that ωP (C 0 , t∗ ) ≥ `v would imply that ωR(>t− ) (Tv , t∗ ) ≥ `v . This in turn
would imply the existence of a pseudo-service of v in the interval (t− , t∗ ] ⊆ (Prevt (v), Nextt (v, i)],
which would contradict the assumption that the service of v at time t is not v-local. (Note that if
t∗ ≤ t− then ωP (C 0 , t∗ ) = 0 as t∗ is before the arrival time of any request in P and the inequality
holds trivially.)
Since P − ∪ P contains all the requests pending at time t, the choice of t∗ and C 0 implies that
ωP − ∪P (C 0 , t∗ ) = `(C 0 ) .

(4)

P − does not contain any requests in C 0 ∩ X − , as those were served at time t− ; therefore
ωP − (C 0 , t∗ ) = ωP − (C 0 − X 0 , t∗ ). Letting B be the set of all nodes w ∈ C 0 − X − for which
S
0
0
parent(w) ∈ X − , we have C 0 − X 0 = w∈B Cw
, where all sets Cw
, for w ∈ B, are disjoint. (See
0
−
Figure 2.) Also, v ∈ C ∩ X . Combining these observations, and using inequalities (3) and (4),

17

Xq

r

v
w
B

C'w
C'

Figure 2: Illustration of the proof of Lemma 5.7.

we get
P

w∈B

S
0
0
, t∗ ) = ωP − ( w∈B Cw
, t∗ )
ωP − (Cw
= ωP − (C 0 − X 0 , t∗ )
= ωP − (C 0 , t∗ )
= ωP − ∪P (C 0 , t∗ ) − ωP (C 0 , t∗ )
> `(C 0 ) − `v
≥ `(C 0 ) − `(C 0 ∩ X − )
P
0
= `(C 0 − X − ) = w∈B `(Cw
).

It follows that there exists w ∈ B such that
0
0
ωP − (Cw
, t∗ ) > `(Cw
).

(5)

−

Equation (5) implies that M t (w) ≤ t∗ , using also the fact that w was not served at t− , so P −
−
contains exactly all the requests used to define M t (w). Let j = depth(w); note that j > i as w is
−
−
a descendant of v. Since w 6∈ X but parent(w) ∈ X − , and M t (w) is finite, the definition of the
extra sets for X − implies that U (v, j, t− ) has sufficient weight and all its nodes are more urgent
−
−
than w. More precisely, `(U (v, j, t− )) ≥ `v and any z ∈ U (v, j, t− ) has M t (z) ≤ M t (w) ≤ t∗ .
It remains to show that every z ∈ U (v, j, t− ) is depth-timely at time t− . Indeed, since
depth(z) = j ≥ i + 1 and any service containing z contains also v, we get
−

−

−

−

Nextt (z, j) ≥ Nextt (z, i + 1) ≥ Nextt (v, i + 1) = Nextt (v, i) > t∗ ≥ M t (z) ,
−

where the last step uses the inequality t∗ ≥ M t (z) derived in the previous paragraph. Thus z is
depth-timely, as needed. The proof of the lemma is now complete.
Competitive analysis. We are now ready to complete our competitive analysis of MLAP.
Theorem 5.8. There exists an O(D4 2D )-competitive algorithm for MLAP on trees of depth D.
Proof. We will show that Algorithm OnlTree’s competitive ratio for L-decreasing trees of depth
D ≥ 3 is at most 4D2 RL , where RL = (2 + 1/L)D−1 . By applying Theorem 3.1, this implies
that there is an online algorithm for arbitrary trees with ratio at most 4D3 L(2 + 1/L)D−1 . For
L = D/2, this ratio is bounded by 3D4 2D , implying the theorem (together with the fact that for
D = 1, 2, constant-competitive algorithms are known).
18

So now we fix an L-decreasing tree T and focus our attention on Algorithm OnlTree’s
schedule S and on the adversary pseudo-schedule S. Define the net charge from a service (X, t)
in S to be the difference between the outgoing and incoming charge of (X, t). Our goal is to show
that each pseudo-service in S is charged only a constant number of times and that the net charge
from each service (X, t) in S is at least `(X)/RL .
Consider first an adversary pseudo-service of v at a time τ . We argue that it is charged at
most (D + 3)`v : If this is the first pseudo-service of v, charged once from both the first service of
v by rule (C1) and from the last service of v at time t = H by rule (C4). In addition, by rule (C1)
it may be charged D times from the last D services of v before τ , and once from the first service
at or after τ . All the charges are equal to `v .
Now consider a service (X, t) of Algorithm OnlTree. For t = H, all the nodes of X have an
outgoing charge by rule (C4) and there is no incoming charge. Thus the net charge from X is
`(X) ≥ `(X)/RL .
For t < H, let X = C ∪ E, where C is the critical subtree and E is the extra set. From
Lemma 5.6, all nodes in C are depth-timely, so they generate outgoing charge of at least `(C)
from X. Next, we show that the net charge from the extra set E is non-negative. Recall that E
is a disjoint union of sets of the form U (w, k, t) and E is disjoint from C. If a future service of a
node v generates the charge of `v to X by rule (C2), it must be the service at time Nextt (v, 1),
so such a charge is unique for each v. Furthermore, Lemma 5.7 implies that one of the extra sets
U (v, j, t), for j > i, has `(U (v, j, t)) ≥ `v and consists of depth-timely nodes only. Thus these
nodes have outgoing charges adding up to at least `v ; these charges go either to the adversary’s
pseudo-services or the algorithm’s services before time t. We have shown that the net charge from
each extra set U (w, k, t) is non-negative; therefore, the net charge from E is non-negative as well.
We conclude that the net charge from X is at least `(C). Applying Lemma 5.4, we obtain that
this net charge is at least `(X)/RL .
Summing over all the services (X, t) in S, we get a bound for the service cost of schedule S:
scost(S) ≤ (D + 3)RL · scost(S). Applying Lemmata 5.3 and 5.5, we get
cost(S) ≤ 2 · scost(S)
≤ 2(D + 3)RL · scost(S)
≤ 2D(D + 3)RL · cost(S∗ ) ≤ 4D2 RL · cost(S∗ ).
We have thus shown that Algorithm OnlTree’s competitive ratio for L-decreasing trees is at
most 4D2 RL , which, as explained earlier, is sufficient to complete the proof.

6

Single-Phase MLAP

We now consider a restricted variant of MLAP that we refer to as Single-Phase MLAP, or 1P-MLAP.
In 1P-MLAP all requests arrive at the beginning, at time 0. The instance also includes a parameter
θ representing the common expiration time for all requests. We do not require that all requests
are served. Any unserved request pays only the cost of waiting until the expiration time θ.
In the online variant of 1P-MLAP, all requests, including their waiting cost functions, are known
to the online algorithm at time 0. The only unknown is the expiration time θ.
Although not explicitly named, variants of 1P-MLAP have been considered in [12, 9], where
they were used to show lower bounds on competitive ratios for MLAP. These proofs consist of
two steps, first showing a lower bound for online 1P-MLAP and then arguing that, in the online
scenario, 1P-MLAP can be expressed as a special case of MLAP. (A corresponding property holds
in the offline case as well, but is quite trivial.) We also use the same general approach in Section 7
to show our lower bounds.
To see that (in spite of the expiration feature) 1P-MLAP can be thought of as a special case
of MLAP, we map an instance J of 1P-MLAP into the instance J 0 of MLAP with the property
19

that any R-competitive algorithm for J 0 can be converted into an R-competitive algorithm for J .
We will explain the general idea when the cost function is linear; the construction for arbitrary
cost functions is based on the same idea, but it involves some minor technical obstacles. Let θ
be the expiration time from J . Choose some large integers K and M . The constructed instance
J 0 consists of K “nested” and “compressed” copies of J , that we also refer to as phases. In the
i-th phase we multiply the waiting cost function of each node by M i . We let this phase start
at time (1 − M −i )θ (that is, at this time the requests from this phase are released) and end
at time θ. Thus the length of phase i is M −i θ. The main trick is that, in J 0 , at time θ the
adversary can serve all pending requests (from all phases) at the cost that is independent of K,
so the contribution of this service cost to the cost of each phase is negligibly small. Following this
idea, any R-competitive algorithm for J 0 can be converted into an R-competitive algorithm for
J , except for some vanishing additive constant. (See [12, 9] for more details.)

6.1

Characterizing Optimal Solutions

Suppose that the expiration value is θ = t. Then the optimal solution is to serve some subtree X
(rooted at r) already at time 0 and wait until the end of the phase at time t with the remaining
requests in X = T − X. So now we consider schedules of this form, that consist of one service
subtree X ⊆ T at time 0. The cost of this schedule (that we identify with X itself) is
cost(X, t) = `(X) + ω(X, t),
P
where, for any set U ⊆ T , ω(U, t) = ρ ωρ (U, t) denotes the waiting cost of all requests in U (see
Section 5.1.)
Our first objective is to characterize those subtrees X that are optimal for θ = t. This
characterization will play a critical role in our online algorithm for 1P-MLAP, provided later
in this section and it also leads to an offline polynomial-time algorithm for computing optimal
solutions, given in Section 6.3.
The lemma below can be derived by expressing 1P-MLAP as a linear program and using strong
duality. We provide instead a simple combinatorial proof. For each subtree Z of T , we denote its
root by rZ . (Also, recall that Zv is the induced subtree of Z rooted at v, that is, Zv contains all
descendants of v in Z.)
Lemma 6.1. A service X is optimal for an expiration time θ = t if and only if it satisfies the
following two conditions:
(a) ω(Xv , t) ≥ `(Xv ) for each v ∈ X, and
(b) ω(Z, t) ≤ `(Z) for each subtree Z, disjoint with X, such that parent(rZ ) ∈ X.
Proof. (⇒) We begin by proving that (a) and (b) are necessary conditions for optimality of X.
(a) Suppose that there is a v ∈ X for which ω(Xv , t) < `(Xv ). Let Y = X − Xv . Then Y is a
service tree (empty if v = r), and we have
cost(Y, t) = `(Y ) + ω(Y , t)
= `(X) − `(Xv ) + ω(X, t) + ω(Xv , t)
< `(X) + ω(X, t) = cost(X, t),
contradicting the optimality of X.
(b) Suppose that there is a subtree Z that violates condition (b), that is Z∩X = ∅, parent(rZ ) ∈
X, but ω(Z, t) > `(Z). Let Y = X ∪ Z. Then Y is a service tree and
cost(Y, t) = `(Y ) + ω(Y , t)
= `(X) + `(Z) + ω(X, t) − ω(Z, t)
< `(X) + ω(X, t) = cost(X, t),
20

contradicting the optimality of X.
(⇐) We now prove sufficiency of conditions (a) and (b). Suppose that X satisfies (a) and
(b), and let Y be any other service subtree of T . From (b), for any node z ∈ Y − X with
parent(z) ∈ X ∩ Y we have ω(Yz , t) ≤ `(Yz ). Since both X and Y are rooted at r, any node in
Y − X is in some induced subtree Yz , for some z such that parent(z) ∈ X ∩ Y . This implies that
ω(Y − X, t) ≤ `(Y − X). Similarly, from (a), for any node v ∈ X − Y with parent(v) ∈ X ∩ Y we
have ω(Xv , t) ≥ `(Xv ). This implies that ω(X − Y, t) ≥ `(X − Y ). These inequalities give us that
cost(Y, t) = `(Y ) + ω(Y , t)
= `(X) + ω(X, t) + [ `(Y − X) − ω(Y − X, t) ] − [ `(X − Y ) − ω(X − Y, t) ]
≥ cost(X, t),
proving the optimality of X.
Following the terminology from Section 5.1, a subtree Z of T (not necessarily rooted at r) is
called mature at time t if ω(Z, t) ≥ `(Z). (We do not need to specify the set of requests in ω(Z, t),
as all requests are released at time 0.) In this section we will simplify this notation and write
“t-mature”, instead of “mature at time t”. We say that Z is t-covered if each induced subtree Zx ,
for x 6= rZ , is t-mature. (Note that in this definition Z itself is not required to be t-mature.) We
now make two observations. First, if Z is t-covered then the definition implies that each induced
subtree Zv of Z is t-covered as well. Two, if Z = {rZ }, that is if Z consists of only one node, then
Z is vacuously t-covered; thus any subtree Z of T has a t-covered subtree rooted at rZ .
Lemma 6.2. If X and Y are t-covered service subtrees of T then the service subtree X ∪ Y is
also t-covered.
Proof. If X = Y the lemma is trivial, so assume X 6= Y . Choose any z ∈ (X − Y ) ∪ (Y − X) with
parent(z) ∈ X ∩ Y . Without loss of generality, we can assume that z ∈ X − Y . By definition, Xz
is t-mature and disjoint with Y .
Take Q = Y ∪ Xz . Q is a service subtree of T . We claim that Q is t-covered. To justify
this claim, choose any v ∈ Q. If v ∈ Y and z ∈
/ Qv , then Qv is t-mature because Qv = Yv . If
v ∈ Qz = Xz then Qv is t-mature because Qv = Xv . The remaining case is when v ∈ Y and
z ∈ Qv . Then ω(Qv , t) = ω(Yv ) + ω(Xz , t) ≥ `(Yv ) + `(Xz ) = `(Qv , t), so Qv is t-mature in this
case as well. Thus indeed Q is t-covered, as claimed.
We can now update Y by setting Y = Q and applying the above argument again. By repeating
this process, we will end up with X = Y , completing the proof.
Choose Ot to be the inclusion-maximal t-covered service subtree of T (that is, a subtree rooted
at r). By Lemma 6.2, Ot is well defined and unique. Also, from Lemma 6.1 we obtain that Ot is
optimal for expiration time θ = t. Thus the optimal cost when θ = t is
t

opt(t) = cost(Ot , t) = `(Ot ) + ω(O , t).
Trivially, if a subtree Z is t-mature and t ≤ t0 then Z is t0 -mature as well. This implies the
following corollary.
0

Corollary 6.3. For every t ≤ t0 it holds that Ot ⊆ Ot .

6.2

An Online Competitive Algorithm

Without loss of generality, we can assume that minv∈T −{r} `v > 1; otherwise the distances together
with the waiting costs can be rescaled to satisfy this property. To simplify the presentation we
will assume that for θ → ∞ the optimum cost grows to ∞. (Any instance can be modified to have
this property, without changing the behavior of the algorithm on T , by adding an infinite path to
the root of T , where the nodes on this path have waiting cost functions that are initially 0 and
then gradually increase.)
21

Algorithm OnlDoubling.
each time ti serve Oti+1 .

For any i ≥ 0, define ti to be the first time when opt(ti ) = 2i . At

Algorithm OnlDoubling is in essence a doubling algorithm [15]. However, although obtaining
some constant ratio using doubling is not difficult, the formulation that achieves the optimal factor
of 4 relies critically on the structure of optimal solutions that we elucidated earlier in this section.
For example, note that the sequence of service costs of the algorithm does not necessarily grow
exponentially.
Analysis. By our assumption that minv∈T −{r} `v > 1, we have Ot0 = {r}; that is, until time
t0 the optimum solution will not make any services and will only pay the waiting cost. This also
implies that ω(Ot0 , t0 ) ≤ 1.
We now estimate the cost of Algorithm OnlDoubling, for a given expiration time θ. Suppose
first that θ = tk , by which we mean that the expiration is right after the algorithm’s service at time
Pk
tk . The total service cost of the algorithm is trivially i=0 `(Oti+1 ). To estimate the waiting cost,
consider some node v. If v ∈ Oti+1 − Oti , for some i = 0, ..., k, then the waiting cost of v is ω(v, ti ).
Otherwise, for v ∈
/ Otk+1 , the waiting cost of v is ω(v, θ) = ω(v, tk ). Thus OnlDoubling’s total
cost is
alg(tk ) =

k
X

`(Oti+1 ) + ω(Ot0 , t0 ) +

i=0

≤

k
X

ω(Oti+1 − Oti , ti ) + ω(O

tk+1

, tk )

i=0

k
X



ti
`(Oti+1 ) + ω(O , ti ) + 1

i=0

≤

k+1
X




ti
`(Oti ) + ω(O , ti ) + 1

i=0

=

k+1
X

opt(ti ) + 1 =

k+1
X

2i + 1 = 2k+2 = 4 · opt(tk ),

i=0

i=0

as needed.
Next, suppose that θ is between two service times, say tk ≤ θ ≤ tk+1 . From the optimality of
tk
θ
Otk at expiration time tk , we have opt(tk ) = `(Otk ) + ω(O , tk ) ≤ `(Oθ ) + ω(O , tk ). Using this
bound, the increase of the optimum cost from time tk to time θ can be estimated as follows:

 

θ
θ
opt(θ) − opt(tk ) ≥ `(Oθ ) + ω(O , θ) − `(Oθ ) + ω(O , tk )
θ

θ

= ω(O , θ) − ω(O , tk ) ≥ ω(O

tk+1

, θ) − ω(O

tk+1

, tk ),

where the last expression is the increase in Algorithm OnlDoubling’s cost from time tk to time
θ. This implies that the ratio at expiration time θ cannot be larger than the ratio at expiration
time tk .
Finally, we have the case when 0 ≤ θ < t0 . Thus opt(θ) < 1. By our assumption that all
weights are greater than 1, this implies that opt(θ) = ω(T , θ), and thus opt(θ) is the same as the
cost of the algorithm.
Summarizing, we obtain our main result of this section.
Theorem 6.4. OnlDoubling is 4-competitive for the Single-Phase MLAP.

6.3

An Offline Polynomial-Time Algorithm

The offline algorithm for computing the optimal solutions is based on the above-established properties of optimal sets Ot . It proceeds bottom up, starting at the leaves, and pruning out subtrees
that are not t-covered. The pseudo-code of our algorithm is shown below.
22

Algorithm 1 CovSubT(v, t)
Av ← {v}
δv ← ω(v, t)
for each child u of v do
(Au , δu ) ← CovSubT(u, t)
if δu ≥ `u then
Av ← Av ∪ Au
δv ← δv + δu − `u
return (Av , δv )

For each node v the algorithm outputs a pair (Av , δv ), where Av denotes the maximal (equivalently w.r.t. inclusion or cardinality) t-covered subtree of v rooted at v, and δv = ω(Av , t) −
`(Av − {v}), that is δv is the “surplus” waiting cost of Av at time t. (Note that we do not account
for `v in this formula.) To compute Ot , the algorithm returns CovSubT(r, t).
By a routine argument, the running time of Algorithm CovSubT is O(N ), where N is the size
of the instance (that is, the number of nodes in T plus the number of requests). Here, we assume
that the values ω(v, t) can be computed in time proportional to the number of requests in v.

7

MLAP on Paths

We now consider the case when the tree is just a path. For simplicity we will assume a generalization to the continuous case, that we refer to as the MLAP problem on the line, when the path
is represented by the half-line [0, ∞); that is the requests can occur at any point x ∈ [0, ∞). Then
the point 0 corresponds to the root, each node is a point x ∈ [0, ∞), and each service is an interval
of the form [0, x]. We say that an algorithm delivers from x if it serves the interval [0, x].
We provide several results for the MLAP problem on the line. We first prove that the competitive ratio of MLAP-D (the variant with deadlines) on the line is exactly 4, by providing matching
upper and lower bounds. Then later we will show that the lower bound of 4 can be modified to
work for MLAP-L (that is, for linear waiting costs).
Algorithm OnlLine. The algorithm creates a service only when a deadline of a pending request
is reached. If a deadline of a request at x is reached, then OnlLine delivers from 2x.
Theorem 7.1. Algorithm OnlLine is 4-competitive for MLAP-D on the line.
Proof. The proof uses a charging strategy. We represent each adversary service, say when the
adversary delivers from a point y, by an interval [0, y]. The cost of each service of OnlLine is
then charged to a segment of one of those adversary service intervals.
Consider a service triggered by a deadline t of a request ρ at some point x. When serving
ρ, OnlLine delivered from 2x. The adversary must have served ρ between its arrival time and
its deadline t. Fix the last such service of the adversary, where at a time t0 ≤ t the adversary
delivered from a point x0 ≥ x. We charge the cost 2x of the algorithm’s service to the segment
[x/2, x] of the adversary’s service interval [0, x0 ] at time t0 .
We now claim that no part of the adversary’s service is charged twice. To justify this claim,
suppose that there are two services of OnlLine, at times t1 < t2 , triggered by requests from points
x1 and x2 , respectively, that both charge to an adversary’s service from x0 at time t0 ≤ t1 . By the
definition of charging, the request at x2 was already present at time t0 . As x2 was not served by
OnlLine’s service at t1 , it means that x2 > 2x1 , and thus the charged segments [x1 /2, x1 ] and
[x2 /2, x2 ] of the adversary service interval at time t0 are disjoint.

23

Summarizing, for any adversary service interval [0, y], its charged segments are disjoint. Any
charged segment receives the charge equal to 4 times its length. Thus this interval receives the
total charge at most 4y. This implies that the competitive ratio is at most 4.
Lower bounds. We now show lower bounds of 4 for MLAP-D and MLAP-L on the line. In both
proofs we show the bound for the corresponding variant of 1P-MLAP, using a reduction from the
online bidding problem [15, 14]. Roughly speaking, in online bidding, for a given universe U of
real numbers, the adversary chooses a secret value u ∈ U and the goal of the algorithm is to
find an upper-bound on u. To this end, the algorithm outputs an increasing sequence of numbers
x1 , x2 , x3 , . . .. The game is stopped after the first xk that is at least u and the bidding ratio is
Pk
then defined as i=1 xi /u.
Chrobak et al. [14] proved that the optimal bidding ratio is exactly 4, even if it is restricted
to sets U of the form {1, 2, . . . , B}, for some integer B. More precisely, they proved the following
result.
Lemma 7.2. For any R < 4, there exists B > 0, such that any sequence of integers 0 = x0 <
Pk
x1 < x2 < . . . < xm−1 < xm = B has an index k ≥ 1 with i=0 xi > R · (xk−1 + 1).
Theorem 7.3. There is no online algorithm for MLAP-D on the line with competitive ratio smaller
than 4.
Proof. We show that no online algorithm for 1P-MLAP-D (the deadline variant of 1P-MLAP) on
the line can attain competitive ratio smaller than 4. Assume the contrary, i.e., that there exists
a deterministic algorithm Alg that is R-competitive, where R < 4. Let B be the integer whose
existence is guaranteed by Lemma 7.2. We create an instance of 1P-MLAP-D, where, at time 0,
for every x ∈ {1, . . . , B} there is a request at x with deadline x.
Without loss of generality, Alg issues services only at integer times 1, 2, ..., B. The strategy
of Alg can be now defined as a sequence of services at times t1 < t2 < . . . < tm , where at time
ti it delivers from xi ∈ {ti , ti + 1, ..., B}. Without loss of generality, x1 < x2 < . . . < xm . We may
assume that xm = B (otherwise the algorithm is not competitive at all); we also add a dummy
service from x0 = 0 at time t0 = 0.
The adversary now chooses some k ≥ 1 and stops the game at the expiration time that is
Pk
right after the algorithm’s kth service, say θ = tk + 21 . Alg’s cost is then i=0 xi . The request
at xk−1 + 1 is not served at time tk−1 , so, to meet the deadline of this request, the schedule of
Alg must satisfy tk ≤ xk−1 + 1. This implies that θ < xk−1 + 2, that is, all requests at points
xk−1 + 2, xk−1 + 3, ..., B expire before their deadlines and do not need to be served. Therefore, to
serve this instance, the optimal solution may simply deliver from xk−1 + 1 at time 0. Hence, the
Pk
competitive ratio of Alg is at least i=0 xi /(xk−1 + 1). By Lemma 7.2, it is possible to choose k
such that this ratio is strictly greater than R, a contradiction with R-competitiveness of Alg.
Next, we show that the same lower bound applies to MLAP-L, the version of MLAP where the
waiting cost function is linear. This improves the lower bound of 3.618 from [9].
Theorem 7.4. There is no online algorithm for MLAP-L on the line with competitive ratio smaller
than 4.
Proof. Similarly to the proof of Theorem 7.3, we create an instance of 1P-MLAP-L (the variant
of 1P-MLAP with linear waiting cost functions) that does not allow a better than 4-competitive
online algorithm. Fix any online algorithm Alg for 1P-MLAP-L and, towards a contradiction,
suppose that it is R-competitive, for some R < 4. Again, let B be the integer whose existence is
guaranteed by Lemma 7.2. In our instance of 1P-MLAP-L, there are 6B−x requests at x for any
x ∈ {1, 2, . . . , B}.
Without loss of generality, we make the same assumptions as in the proof of Theorem 7.3:
algorithm Alg is defined by a sequence of services at times 0 = t0 < t1 < t2 < . . . < tm , where
24

at each time ti it delivers from some point xi . Without loss of generality, we can assume that
0 = x0 < x1 < . . . < xm = B.
Again, the strategy of the adversary is to stop the game at some expiration time θ that is right
Pk
after some time tk , say θ = tk + , for some small  > 0. The algorithm pays i=0 xi for serving
the requests. The requests at xk−1 + 1 waited for time tk in Alg’s schedule and hence Alg’s
waiting cost is at least 6B−xk−1 −1 · tk .
The adversary delivers from point xk−1 + 1 at time 0. The remaining, unserved requests
PB
at points xk−1 + 2, xk−1 + 3, . . . , B pay time θ each for waiting. There are j=xk−1 +2 6B−j ≤
1 B−xk−1 −1
such requests and hence the adversary’s waiting cost is at most 15 ·6B−xk−1 −1 ·(tk +).
5 ·6
Therefore, the algorithm-to-adversary ratio on the waiting costs is at least 5tk /(tk + ). For
any k we can choose a sufficiently small  so that this ratio is larger than 4. By Lemma 7.2, it is
possible to choose k for which the ratio on servicing cost is strictly greater than R. This yields a
contradiction to the R-competitiveness of Alg.
We point out that the analysis in the proof above gives some insight into the behavior of
any 4-competitive algorithm for 1P-MLAP-L (we know such an algorithm exists, by the results in
Section 6), namely that, for the type of instances used in the above proof, its waiting cost must
be negligible compared to the service cost.

8

An Offline 2-Approximation Algorithm for MLAP-D

In this section we consider the offline version of MLAP-D, for which Becchetti et al. [5] gave
a polynomial-time 2-approximation algorithm based on LP-rounding. We give a much simpler
argument that does not rely on linear programming.
We will use an alternative specification of schedules that is easier to reason about in the context
of offline approximations. If S is a schedule, for each node x ∈ T we can specify the set Sx of times
t for which S contains a service (X, t) with x ∈ X. Then the set {Sx }x∈T uniquely determines S.
Note that we have Sx ⊆ Sy whenever y is the parent of x. Further, we can now write the service
P
cost as scost(S) = x∈T |Sx |`x . It is easy to see that (without loss of generality) in an optimal
(offline) schedule S each service time is equal to some deadline, and we will make this assumption
in this section; in particular, Sr can be assumed to be the set of all deadlines.
Let J be the given instance. For each node v, define Jv to be the set of all intervals [aρ , dρ ],
for requests ρ issued in Tv .
Algorithm OffLByL. We proceed level by level, starting at the root and in order of increasing
depth, computing the service times Sv for all nodes v ∈ T . For the root r, Sr is the set of the
deadlines of all requests. Consider now some node v with parent u for which Su has already
been computed. Using the standard earliest-deadline algorithm, compute Sv as the minimum
cardinality subset of Su that intersects all intervals in Jv .
Algorithm OffLByL clearly runs in polynomial time; in fact it can be implemented in time
O(N log N ), where N is the total size of J .
We now show that the approximation ratio of Algorithm OffLByL is at most 2. (It is easy to
find an example showing that this ratio is not better than 2.) Denote by S∗ an optimal schedule
for J . According to our convention, S∗v is then the set of times when v is served in S∗ . Since
P
P
cost(S) = v `v |Sv | and the optimum cost is cost(S∗ ) = v `v |S∗v |, it is sufficient to show that
|Sv | ≤ 2|S∗v | for each v 6= r. This is quite simple: if u is the father of v then Su intersects all
intervals in Jv . We construct S0v ⊆ Su as follows. For each t ∈ S∗v , choose the maximal t− ∈ Su
such that t− ≤ t, and the minimal t+ ∈ Su such that t+ ≥ t. Add t− , t+ to S0v . (More precisely,
each of them is added only if it is defined.) Then S0v ⊆ Su and |S0v | ≤ 2|S∗v |. Further, any
interval [aρ , dρ ] ∈ Jv contains some t ∈ S∗v and intersects Su , so it also must contain either t−

25

or t+ . Therefore S0v intersects all intervals in Jv . Since we pick Sv optimally from Su , we have
|Sv | ≤ |S0v | ≤ 2|S∗v |, completing the proof.

9

General Waiting Costs

Our model of MLAP assumes full continuity, namely that the time is continuous and that the
waiting costs are continuous functions of time, while in some earlier literature authors use the
discrete model. Thus we still need to show that our algorithms can be applied in the discrete
model without increasing their competitive ratios. We also consider the model where some request
may remain unserved. We explain how our results can be extended to these models as well. We
will also show that our results can be extended to functions that are left-continuous, and that
MLAP-D can be represented as a special case of MLAP with left-continuous functions. While those
reductions seem intuitive, they do involve some pesky technical challenges, and they have not been
yet formally treated in the literature.
Extension to the discrete model. In the discrete model (see [12], for example), requests
arrive and services may happen only at integral points t = 1, . . . , H, where H is the time horizon.
The waiting cost functions ωρ are also specified only at integral points. (The model in [12] also
allows waiting costs to be non-zero at the release time. However we can assume that ωρ (aρ ) = 0,
since increasing the waiting cost function uniformly by an additive constant can only decrease the
competitive ratio.)
We now show how to simulate the discrete time model in the model where time and waiting
costs are continuous. Suppose that A is an R-competitive online algorithm for the model with
continuous time and continuous waiting cost functions. We construct an R-competitive algorithm
B for the discrete time model.
Let J = hT , Ri be an instance given to B. We extend each waiting cost function ωρ to nonintegral times as follows: for each integral t = aρ , . . . , H − 1 we define ωρ (τ ) for τ ∈ (t, t + 1) so
that it continuously increases from ωρ (t) to ωρ (t + 1) (e.g., by linear interpolation); ωρ (τ ) = 0 for
all τ < aρ ; and ωρ (τ ) = ωρ (H) for all τ > H.
Algorithm B presents the instance J = hT , Ri with these continuous waiting cost functions
to A. At each integral time t = 1, . . . , H − 1, B simulates A on the whole interval [t, t + 1). If
A makes one or more services, B makes a single service at time t which is their union. This is
possible, since no request arrives in (t, t + 1). At time H, algorithm B issues the same service as
A.
Overall, B produces a feasible schedule in the discrete time model. The cost of B does not
exceed the cost of A. On the other hand, any feasible (offline) schedule S in the discrete time
model is also a feasible schedule in the continuous time model with the same cost. Thus B is
R-competitive.
Unserved requests with bounded waiting costs. In our definition of MLAP we require that
all the requests are eventually served. However, if the waiting cost of a request ρ is bounded, it
is natural to allow a possibility that ρ is not served in a schedule S; in that case it incurs waiting
cost wcost(ρ, S) = limt→+∞ ωρ (t). In this variant, there is no time horizon in the instance.
Our algorithm OnlTree works in this model as well, with the competitive ratio increased at
most by one. The only modification of the algorithm is that there is no final service at the time
horizon. Instead we let the time proceed to infinity, issuing services at the maturity times of q
(the quasi-root of T ).
To modify our charging scheme to this variant, the key observation is that if a node v is never
serviced both in OnlTree and in an optimal schedule S∗ , then the requests at v pay the same
waiting costs in both schedules. Thus we can ignore such nodes and requests at them. We claim

26

that for each remaining node v, the pseudo-schedule S contains at least one pseudo-service of v:
Indeed, otherwise v is not served in S∗ and the total (limit of the) waiting cost of all the (unserved)
requests in the induced subtree Tv is less than `v , which implies that the maturity time of v is
always infinite and thus v is never serviced in OnlTree either, contradicting the fact that v was
not ignored before. Now consider all the remaining unserved requests and add to the schedule of
OnlTree one last service that serves all these requests. As the unserved requests do not cause
q to mature, this increases the cost of OnlTree; at the same time the service of each node can
be charged to a pseudo-service of the same node in S, which increases the competitive ratio by at
most 1.
Extension to left-continuous waiting costs. We now argue that we can modify our algorithms to handle left-continuous waiting cost functions, i.e., functions that satisfy limτ %t ωρ (τ ) =
ωρ (t) for each time t ≥ 0. Left-continuity enables an online algorithm to serve a request at the
last time when its waiting cost is at or below some given threshold.
Some form of left-continuity is also necessary for constant competitiveness. To see this, think
of a simple example of a tree of depth 1 and with `q = 1, and a sequence of requests in q with
release times approaching 1, and waiting cost functions defined by ωρ (1) = K  1 and ωρ (t) = 0
for t < 1. If an online algorithm serves one such request before time 1, the adversary immediately
releases another. The sequence stops either after K requests or after the algorithm serves some
request at or after time 1, whichever comes first. The optimal cost is at most `q = 1, while the
online algorithm pays at least K.
The basic (but not quite correct) idea of our argument for left-continuous waiting cost functions
is this: For any time point h where some waiting cost function has a discontinuity, we replace
point h by a “gap interval” [h, h + ], for some  > 0. The release times after time h and the values
of all waiting cost functions after h are shifted to the right by . In the interval [h, h + ], for
each request ρ, its waiting cost function is filled in by any non-decreasing continuous curve with
value ν − at h and ν + at h + , for ν − = ωρ (h) and ν + = limτ &h ωρ (τ ). Thus the waiting cost
functions that are continuous at h are simply “stretched” in this gap interval, where their values
remain constant. This will convert the original instance J into an instance J 0 with continuous
waiting cost functions; then we can apply a simulation similar to the one for the discrete model,
with the behavior of an algorithm A on J 0 inside [h, h + ] mimicked by the algorithm B on J
while staying at time h.
The above construction, however, has a flaw: as B is online, for each newly arrived request ρ
it would need to know the future requests in order to correctly modify ρ’s waiting cost function
(which needs to be fully revealed at the arrival time). Thus, inevitably, B will need to be able to
modify waiting cost functions of earlier requests, but the current state of A may depend on these
functions. Such changes could make the computation of A meaningless. To avoid this problem,
we will focus only on algorithms A for continuous cost functions that we call stretch-invariant.
Roughly, those are algorithms whose computation is not affected by the stretching operation
described above.
To formalize this, let I = {[hi , hi + εi ] | i = 1, . . . , k} be a finite set of gap intervals, where all
times hi are distinct. (For now we can allow the εi ’s to be any positive reals; their purpose will be
P
explained later.) Let shift(t, I) = t+ i:hi <t εi denote the time t shifted right by inserting intervals
I on the time axis. We extend this operation to requests in a natural way: for any request ρ with
a continuous waiting cost function, shift(ρ, I) denotes the request modified by inserting I on the
time axis and filling in the values of ωρ in the inserted intervals by constant functions, as described
earlier. For a set of requests P ⊆ R, the stretched set of requests shift(P, I) is the set consisting
of requests shift(ρ, I), for all ρ ∈ P .
Consider an online algorithm A for MLAP with continuous waiting cost functions. We say that
A is stretch-invariant if for every instance J = hT , Ri and any set of gap intervals I, the schedule
produced by A for the instance hT , shift(R, I)i is obtained from the schedule produced by A for
27

J by shifting it according to I, namely every service (X, t) is replaced by service (X, shift(t, I)).
Most natural algorithms for MLAP are stretch-invariant. In case of OnlTree, observe that its
behavior depends only on the maturity times MP (v) where P is the set of pending requests and
Mshift(P,I) (v) = shift(MP (v), I); in particular stretching does not change the order of the maturity
times. Using induction on the current time t, we observe OnlTree creates a service (X, t) in
its schedule for the request set R if and only if OnlTree creates a service (X, shift(t, I)) in its
schedule for the request set shift(R, I).
Suppose that A is an R-competitive online algorithm for continuous waiting cost functions that
is stretch-invariant. We convert A into an R-competitive algorithm B for left-continuous waiting
costs. Let J = hT , Ri be an instance given to B. Algorithm B maintains the set of gap intervals
I, and a set of requests P presented to A; both sets are initially empty. Algorithm B at time t
simulates the computation of A at time shift(t, I).
If a new request ρ ∈ R is released at time t = aρ , algorithm B obtains ρ0 from shift(ρ, I)
by replacing the discontinuities of ωρ by new gap intervals Iρ on which ωρ0 is defined so that it
continually increases. (If a gap interval already exists in I at the given point, it is used instead of
creating a new one, to maintain the starting points distinct.) We set aρ0 = shift(t, I), which is the
current time in A. We update I to I ∪ Iρ ; this does not change the current time in A as all new
gap intervals start at or after t. We stretch the set of requests P by Iρ ; this does not change the
past output of A, because A is stretch-invariant. (Note that the state of A at time t may change,
but this does not matter for the simulation.) Finally, we add the new request ρ0 to P.
If the current time t in B is at a start point of a gap interval, i.e., t = hi , algorithm B simulates
the computation of A on the whole shifted gap interval hshift(hi , I), εi i. If A makes one or more
services in hshift(hi , I), εi i, B makes a single service at time t which is their union.
The cost of B for requests R does not exceed the cost of A for requests P. Any adversary
schedule S for R induces a schedule S0 for P with the same cost. Since A’s cost is at most
R · cost(S0 ), we obtain that B’s cost is at most R · cost(S); hence B is R-competitive.
In the discussion above we assumed that the instance has a finite number of discontinuities.
Arbitrary left-continuous waiting cost functions may have infinitely many discontinuity points, but
the set of these points must be countable. The construction described above extends to arbitrary
left-continuous cost functions, as long as we choose the εi values so that their sum is finite.
Reduction of MLAP-D to MLAP. We now argue that MLAP-D can be expressed as a variant of
MLAP with left-continuous waiting cost functions. The idea is simple: a request ρ with deadline
dρ can be assigned a waiting cost function ωρ (t) that is 0 for times t ∈ [0, dρ ] and ∞ for t > dρ
– except that we cannot really use ∞, so we need to replace it by some sufficiently large number.
If σρ = v, we let ωρ (t) = `∗v , where `∗v is the sum of all weights on the path from v to r (the
“distance” from v to r). This will convert an instance J of MLAP-D into an instance J 0 of MLAP
with left-continuous waiting cost functions.
We claim that, without loss of generality, any online algorithm A for J 0 serves any request ρ
before or at time dρ . Otherwise, A would have to pay waiting cost of `∗v for ρ (where v = σρ ), so
we can modify A to serve ρ at time dρ instead, without increasing its cost. We can then treat A
as an algorithm for J . A will meet all deadlines in J and its cost on J will be the same as its
cost on J 0 , which means that its competitive ratio will also remain the same.
Note that algorithm OnlTree (or rather its extension to the left-continuous waiting costs, as
described above) does not need this modification, as it already guarantees that when the waiting
cost of a request at v reaches `∗v , all the nodes on the path from v to r are mature and thus the
whole path is served.

28

References
[1] A. Aggarwal and J. K. Park. Improved algorithms for economic lot sizing problems. Operations
Research, 41:549–571, 1993.
[2] S. Albers and H. Bals. Dynamic TCP acknowledgment: Penalizing long delays. SIAM Journal
on Discrete Mathematics, 19(4):938–951, 2005.
[3] E. Arkin, D. Joneja, and R. Roundy. Computational complexity of uncapacitated multiechelon production planning problems. Operations Research Letters, 8(2):61–66, 1989.
[4] B. R. Badrinath and P. Sudame. Gathercast: the design and implementation of a programmable aggregation mechanism for the internet. In Proc. 9thInternational Conference on
Computer Communications and Networks (ICCCN), pages 206–213, 2000.
[5] L. Becchetti, A. Marchetti-Spaccamela, A. Vitaletti, P. Korteweg, M. Skutella, and L. Stougie.
Latency-constrained aggregation in sensor networks. ACM Transactions on Algorithms,
6(1):13:1–13:20, 2009.
[6] M. Bienkowski, M. Böhm, J. Byrka, M. Chrobak, C. Dürr, L. Folwarczný, L. Jez, J. Sgall,
N. K. Thang, and P. Veselý. Online algorithms for multi-level aggregation. In Proc. 24th
Annual European Symposium on Algorithms (ESA’16), pages 12:1–12:17, 2016.
[7] M. Bienkowski, J. Byrka, M. Chrobak, N. B. Dobbs, T. Nowicki, M. Sviridenko, G. Swirszcz,
and N. E. Young. Approximation algorithms for the joint replenishment problem with deadlines. Journal of Scheduling, 18(6):545–560, 2015.
[8] M. Bienkowski, J. Byrka, M. Chrobak, L. Jeż, D. Nogneng, and J. Sgall. Better approximation
bounds for the joint replenishment problem. In Proc. 25th ACM-SIAM Symp. on Discrete
Algorithms (SODA), pages 42–54, 2014.
[9] M. Bienkowski, J. Byrka, M. Chrobak, L. Jeż, J. Sgall, and G. Stachowiak. Online control
message aggregation in chain networks. In Proc. 13th Int. Workshop on Algorithms and Data
Structures (WADS), pages 133–145, 2013.
[10] E. Bortnikov and R. Cohen. Schemes for scheduling of control messages by hierarchical
protocols. In Proc. 17th IEEE Int. Conference on Computer Communications (INFOCOM),
pages 865–872, 1998.
[11] C. Brito, E. Koutsoupias, and S. Vaya. Competitive analysis of organization networks or
multicast acknowledgement: How much to wait? Algorithmica, 64(4):584–605, 2012.
[12] N. Buchbinder, T. Kimbrel, R. Levi, K. Makarychev, and M. Sviridenko. Online make-to-order
joint replenishment model: Primal-dual competitive algorithms. In Proc. 19th ACM-SIAM
Symp. on Discrete Algorithms (SODA), pages 952–961, 2008.
[13] N. Buchbinder and J. S. Naor. The design of competitive online algorithms via a primal-dual
approach. Foundations and Trends in Theoretical Computer Science, 3(2–3):93–263, 2009.
[14] M. Chrobak, C. Kenyon, J. Noga, and N. E. Young. Incremental medians via online bidding.
Algorithmica, 50(4):455–478, 2008.
[15] M. Chrobak and C. Kenyon-Mathieu. SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News, 37(4):115–126, 2006.
[16] W. B. Crowston and M. H. Wagner. Dynamic lot size models for multi-stage assembly systems.
Management Science, 20(1):14–21, 1973.
29

[17] D. R. Dooly, S. A. Goldman, and S. D. Scott. On-line analysis of the TCP acknowledgment
delay problem. Journal of the ACM, 48(2):243–273, 2001.
[18] J. S. Frederiksen, K. S. Larsen, J. Noga, and P. Uthaisombut. Dynamic TCP acknowledgment
in the LogP model. Journal of Algorithms, 48(2):407–428, 2003.
[19] F. Hu, X. Cao, and C. May. Optimized scheduling for data aggregation in wireless sensor
networks. In Int. Conference on Information Technology: Coding and Computing (ITCC),
volume 2, pages 557–561, 2005.
[20] A. R. Karlin, C. Kenyon, and D. Randall. Dynamic TCP acknowledgement and other stories
about e/(e - 1). Algorithmica, 36(3):209–224, 2003.
[21] S. Khanna, J. Naor, and D. Raz. Control message aggregation in group communication
protocols. In Proc. 29th Int. Colloq. on Automata, Languages and Programming (ICALP),
pages 135–146, 2002.
[22] A. Kimms. Multi-Level Lot Sizing and Scheduling: Methods for Capacitated, Dynamic, and
Deterministic Models. Springer-Verlag, 1997.
[23] D. M. Lambert and M. C. Cooper. Issues in supply chain management. Industrial Marketing
Management, 29(1):65–83, 2000.
[24] R. Levi, R. Roundy, and D. B. Shmoys. A constant approximation algorithm for the onewarehouse multi-retailer problem. In Proc. 16th ACM-SIAM Symp. on Discrete Algorithms
(SODA), pages 365–374, 2005.
[25] R. Levi, R. Roundy, and D. B. Shmoys. Primal-dual algorithms for deterministic inventory
problems. Mathematics of Operations Research, 31(2):267–284, 2006.
[26] R. Levi, R. Roundy, D. B. Shmoys, and M. Sviridenko. A constant approximation algorithm
for the one-warehouse multiretailer problem. Management Science, 54(4):763–776, 2008.
[27] R. Levi and M. Sviridenko. Improved approximation algorithm for the one-warehouse multiretailer problem. In Proc. 9th Int. Workshop on Approximation Algorithms for Combinatorial
Optimization (APPROX), pages 188–199, 2006.
[28] T. Nonner and A. Souza. Approximating the joint replenishment problem with deadlines.
Discrete Mathematics, Algorithms and Applications, 1(2):153–174, 2009.
[29] C. Papadimitriou. Computational aspects of organization theory. In Proc. 4th European
Symp. on Algorithms (ESA), pages 559–564, 1996.
[30] L. L. C. Pedrosa. Private communication, 2013.
[31] S. S. Seiden. A guessing game and randomized online algorithms. In Proc. 32nd ACM Symp.
on Theory of Computing (STOC), pages 592–601, 2000.
[32] S. Vaya. Brief announcement: Delay or deliver dilemma in organization networks. In Proc.
31st ACM Symp. on Principles of Distributed Computing (PODC), pages 339–340, 2012.
[33] H. Wagner and T. Whitin. Dynamic version of the economic lot size model. Management
Science, 5:89–96, 1958.
[34] W. Yuan, S. V. Krishnamurthy, and S. K. Tripathi. Synchronization of multiple levels of
data fusion in wireless sensor networks. In Proc. Global Telecommunications Conference
(GLOBECOM), pages 221–225, 2003.

30

