## 1 Introduction
Usually, the sizes of subnets requested by users depend on the number of computers they want to connect to the subnet, and the task of system managers is to assign subnets to users so that no two assigned subnets overlap. Apparently, we want to minimize the number of reassignments because a reassignment causes a large cost for updating configurations of computers. Our Contribution.In this paper, we improve both upper and lower bounds on the competitive ratio of this problem, namely, we give a 7-competitive algorithm Extended-Lazy, and show that no online algorithm can be better than 2-competitive. We further show that our upper bound analysis is tight by giving a sequence of requests for which the competitive ratio of Extended-Lazy is \(7-\varepsilon\) for an arbitrary constant \(\varepsilon>0\). We briefly explain an idea of improving the upper bound. [PERSON] _et al._[4] defined the \"compactness\" of assignments, and their algorithm keeps an assignment compact at any time. They proved that serving a request, namely assigning (or removing) a code and modifying the assignment to keep it compact, will cause at most one reassignment at each level, which leads to \(\Theta(h)\)-competitiveness. [PERSON], [PERSON], and [PERSON] [6] pointed out that always keeping assignments compact is too costly. Their algorithm LAZY does not always keep compactness but makes assignments compact when it is necessary. To achieve this relaxation, they defined a \"tank\", which is a vertex that _virtually_ contains a code of a lower level. By exploiting the idea of tanks, they proved that the cost of serving each request is at most 5, which results in 10-competitiveness. Our algorithm, called Extended-Lazy, follows this line. We further relax the compactness by defining \"semi-compactness\". We also use amortized cost analysis, and prove that serving one insertion (deletion, respectively) and keeping the semi-compactness costs at most 4 (3, respectively). This gives a 7-competitiveness of Extended-Lazy. Related Results.For the online OVSF code assignment problem, there have been some resource augmentation models, namely, online algorithms are allowed to use more bandwidth than an optimal offline algorithm: [PERSON] _et al._[4] developed a 4-competitive algorithm in which an online algorithm can use a double-sized OVSF code tree. [PERSON], [PERSON], and [PERSON] [7] developed a 5-competitive algorithm that uses 1/8 extra bandwidth. Recently, [PERSON] _et al._[8] gave a 1-competitive online algorithm which uses \((h+1)/2\) trees and showed that there is no 1-competitive online algorithm that uses less than \((h+1)/2\) trees. They also gave a 2-competitive algorithm with \(3h/8+2\) trees and an amortized \((4/3+\alpha)\)-competitive algorithm with \((11/4+4/(3\alpha))\) trees, for any \(\alpha\) where \(0<\alpha\leq 4/3\). In addition to theoretical analysis, [PERSON] and [PERSON] [9] evaluated the performance of genetic algorithm and simulated annealing by experiments. Also, there have been several _offline_ results. [PERSON] and [PERSON] [10] developed a greedy algorithm for the problem of finding the minimum number of reassignments to modify the current assignment so that the new code can be assigned, given a current assignment configuration of the tree and a new insertion request. Moreover, [PERSON] _et al._[4] proved that this problem is NP-hard and developed a \(\Theta(h)\)-approximation algorithm. [PERSON], [PERSON], and [PERSON] [11] proved that the problem of finding a sequence of operations that minimizes the number of reassignments, given an OVSF code tree and a whole sequence of requests, is NP-hard and gave an exponential-time algorithm.