The combinatorial core of the OVSF code assignment problemthat arises in UMTS is to assign some nodes of a complete binarytree of height h (the code tree) to n simultaneous connections, such thatno two assigned nodes (codes) are on the same root-to-leaf path. Eachconnection requires a code on a specified level. The code can change overtime as long as it is still on the same level. We consider the one-step codeassignment problem: Given an assignment, move the minimum number ofcodes to serve a new request. Minn and Siu proposed the so-called DCAalgorithmto solve the problem optimally. We show that DCA does notalways return an optimal solution, and that the problem is NP-hard.We give an exact nO(h)-time algorithm, and a polynomial time greedyalgorithm that achieves approximation ratio Θ(h). Finally, we considerthe online code assignment problem for which we derive several results
京公网安备 11010802033920号
Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved
评论