## 2 Preliminaries  
An instance of the online OVSF problem consists of an OVSF code tree of height \(h\) and a sequence \(\sigma\) of requests. Each request is either an _insertion_ or a _deletion_. An insertion \(i_{c}\) specifies a code \(c\). Upon receiving an insertion \(i_{c}\), the task of an online algorithm is to assign \(c\) to one of the vertices of level \(\ell(c)\) (i.e. the level specified by \(c\)) of the OVSF code tree, so that the orthogonality condition is not broken. An online algorithm may also reassign other codes (already existing in the tree). A deletion \(d_{c}\) specifies a code \(c\) which was previously assigned and has still been assigned to the current OVSF code tree. When a deletion \(d_{c}\) arrives, the task of an online algorithm is to merely remove \(c\) from the tree (and similarly, it may reassign other codes in the tree). Each assignment and reassignment causes a cost of one, but removing a code causes no cost. Without loss of generality, we may assume that \(\sigma\) does not include an insertion that cannot be assigned by any reassignment of the existing codes (in other words, the total bandwidth of codes which should be assigned at any point never exceeds the capacity). We define terminologies needed to give our algorithm, most of which are taken from [6]. Given an assignment configuration, we say that vertex \(v\) is _assignable_ if none of descendants, ancestors, or \(v\) itself is assigned; in other words, a code can be assigned to \(v\) without breaking the orthogonality. We also say that vertex \(v\) is _dead_ if \(v\) or one of its descendants is assigned. In the example of Figure 2, shaded vertices are assigned, vertices with pluses (\(+\)) are assignable, and vertices with stars (\(*\)) are dead. Note that assignable vertices are all non-dead. If all the assigned vertices are mutually orthogonal and, at any level, all the left vertices (on the same level) to the rightmost dead vertex are dead, then the assignment is called _compact_. For example, the assignment in Figure 2 is compact. Next, we define statuses of levels. Level \(\ell\) is said to be _rich_ if a code of level \(\ell\) can be assigned to the leftmost non-dead vertex \(v\) at \(\ell\) without reassigning other codes; in other words, \(v\) is assignable. Otherwise, the level \(\ell\) is said to be _poor_. For example, in the assignment of Figure 2, levels 0, 2, and 3 are rich and levels 1 and 4 are poor. A level \(\ell\) is said to be _locally rich_ if the rightmost assigned vertex is the left child of its parent. For example, in Figure 2, only level 0 is locally rich. Note that in a compact assignment, locally rich levels are always rich. Figure 2: A compact assignment. We introduce a tank, which is taken from [6]: Suppose that two codes \(c_{1}\) and \(c_{2}\) of level 0 arrive when the current configuration is in Figure 2. We can assign \(c_{1}\) to the leftmost assignable vertex of level 0 with keeping the compactness. However, we cannot assign \(c_{2}\) with keeping the compactness unless we reassign other codes. If \(c_{2}\) were a code of level 2, it could be assigned to the leftmost assignable vertex of level 2 without breaking the compactness. The idea of a tank is to do this virtually. See Figure 3 for example. The code \(c_{2}\) is assigned to \(x\), but we consider as if it were assigned to \(y\), and by doing so, we regard the assignment compact. Formally, we virtually assign a code of level \(b\) to a vertex \(v\) of higher level \(t\) (\(>b\)). In this case, \(v\) is called a tank and denoted tank[\(b,t\)]. Levels \(b\) and \(t\) are called the _bottom_ and the _top_ of tank[\(b,t\)], respectively. We say that level \(\ell\)\((b\leq\ell\leq t)\)_belongs to_ tank[\(b,t\)]. Note that in the definitions and proofs below, we regard \(y\) as \"assigned\" and \(x\) as \"unassigned\". We also define the _semi-compactness_.