 |
|
|||
| Authors: | Thomas Erlebach, Riko Jacob, Matus Mihalak, Marc Nunkesser, Gabor Szabo, Peter Widmayer |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | An Algorithmic View on OVSF Code Assignment |
| Year: | 2004 |
| Month: | March |
| Pub-Key: | EJMNSW04 |
| Book Titel: | Lecture Notes in Computer Science. Proceedings of the 21st Symposium on Theoretical Aspect of Computer Science (STACS) |
| Volume: | 2996 |
| Pages: | 270-281 |
| Publisher: | Springer-Verlag |
| Abstract: | 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 DCA-algorithm 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 n^{O(h)}-time algorithm, and a polynomial time greedy algorithm that achieves approximation ratio Theta(h). Finally, we consider the online code assignment problem for which we derive several results. |
| Location: | Montpellier, France |
| Resources: | [BibTeX] |
