## 1 Introduction  
Universal Mobile Telecommunication System (UMTS) [1; 2] is one of the third generation (3G) technologies, which is a mobile communication standard. UMTS uses a high-speed transmission protocol Wideband Code Division Multiple Access (W-CDMA) as the primary mobile air interface. W-CDMA is implemented based on Direct Sequence CDMA (DS-CDMA), which allows several users to communicate simultaneously over a single communication channel. DS-CDMA utilizes Orthogonal Variable Spreading Factor (OVSF) code to separate communications [3]. OVSF code is based on an _OVSF code tree_, which is a complete binary tree of height \(h\). The leaves of the OVSF code tree are of level 0 and parents of vertices of level \(\ell\)\((\ell=0,\ldots,h-1)\) are of level \(\ell+1\). Therefore the level of the root is \(h\). Figure 1 shows an OVSF code tree of height 4. (Ignore \"\(c_{1},\ldots,c_{4}\)\" and shaded vertices for a while. We use them later.) Each vertex of level \(\ell\) corresponds to a code of level \(\ell\). In DS-CDMA, each communication uses a code of the specific level. To avoid interference, we need to assign codes to vertices of an OVSF code tree so that they are _mutually orthogonal_, namely, in any path from the root to a leaf of an OVSF code tree, there is at most one assigned vertex. For example, consider the OVSF code tree given in Figure 1. Let \(\ell(c)\) denote the level specified by a code \(c\). Suppose that four requests for inserting codes \(c_{1}\), \(c_{2}\), \(c_{3}\), and \(c_{4}\) such that \(\ell(c_{1})=2\), \(\ell(c_{2})=\ell(c_{3})=1\), \(\ell(c_{4})=0\) arrive in this order, and that they are assigned as depicted in Figure 1. Then, a request for deleting \(c_{2}\) arrives and \(c_{2}\) is removed. Next, a request for inserting \(c_{5}\) such that \(\ell(c_{5})=3\) arrives, but it cannot be assigned unless other codes are reassigned. If \(c_{4}\) is reassigned to one of the children of the vertex to which \(c_{2}\) was assigned, we can assign \(c_{5}\) to the right vertex of level 3. In this case, we need 6 assignments (5 assignments and 1 reassignment). However, if \(c_{2}\) has been assigned to a vertex in the right subtree of the root, and \(c_{4}\) has been assigned to a vertex in the left subtree, then we need only 5 assignments. [PERSON] _et al._[4] first modeled this problem as an online problem of minimizing the number of assignments, called the online OVSF code assignment problem, and verified the efficiency of online algorithms using competitive analysis. The _competitive ratio_ of an online algorithm \(ALG\) is defined as \(\max_{\sigma}\{\frac{E_{ALG}(\sigma)}{E_{OPT}(\sigma)}\}\), where \(E_{ALG}(\sigma)\) and \(E_{OPT}(\sigma)\) are the costs of \(ALG\) and an optimal offline algorithm, respectively, for a sequence \(\sigma\) of requests, and \(\max\) is taken over all \(\sigma\). For the online OVSF code assignment problem, the number of assignments is regarded as a cost. If the competitive ratio of \(ALG\) is at most \(\alpha\), we say that \(ALG\) is \(\alpha\)-competitive. [PERSON] _et al._[4] developed a \(\Theta(h)\)-competitive algorithm (recall that \(h\) is the height of an OVSF code tree), and proved that the lower bound on the competitive ratio of the problem is 1.5. [PERSON] _et al._[5] developed a \(\Theta(1)\)-competitive algorithm, but they did not obtain a concrete constant. [PERSON], [PERSON], and [PERSON] [6] proposed algorithm LAZY by modifying the algorithm of [PERSON] _et al._[4], and proved that the competitive ratio of LAZY is at most 10. [PERSON], [PERSON], and [PERSON] [6] also showed that no online algorithm can be better than 5/3-competitive. Figure 1: An OVSF code tree of height 4. This problem also has an application in assigning subnets to users in computer network managements. An IP address space can be divided into subnets, each of which is a fragment of the whole IP address space consisting of a set of continuous IP addresses of size power of 2. This structure can be represented as a complete binary tree, in exactly the same way as our problem.