虫虫首页|资源下载|资源专辑|精品软件
登录|注册

您现在的位置是：虫虫下载站 > 资源下载 > 其他书籍 > The combinatorial core of the OVSF code assignment problem that arises in UMTS is to assign some no

The combinatorial core of the OVSF code assignment problem that arises in UMTS is to assign some no

资 源 简 介

The combinatorial core of the OVSF code assignment problem that arises in UMTS is to assign some nodes of a complete binary tree of height h (the code tree) to n simultaneous connections, such that no two assigned nodes (codes) are on the same root-to-leaf path. Each connection requires a code on a specified level. The code can change over time as long as it is still on the same level. We consider the one-step code assignment problem: Given an assignment, move the minimum number of codes to serve a new request. Minn and Siu proposed the so-called DCAalgorithm to solve the problem optimally. We show that DCA does not always return an optimal solution, and that the problem is NP-hard. We give an exact nO(h)-time algorithm, and a polynomial time greedy algorithm that achieves approximation ratio Θ(h). Finally, we consider the online code assignment problem for which we derive several results

相 关 资 源

您 可 能 感 兴 趣 的

虫虫下载站版权所有 京ICP备2021023401号-1