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
评论