Solving Frequency Assignment Problems via Tree-Decomposition1
| Autor: | Stan P. M. van Hoesel, Antoon W. J. Kolen, Arie M. C. A. Koster |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Dynamic programming
Mathematical optimization Bounding overwatch Applied Mathematics Frequency assignment Discrete Mathematics and Combinatorics Graph (abstract data type) Frequency assignment problem Algorithm Tree decomposition Generalized assignment problem Weapon target assignment problem Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics. 3:102-105 |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/s1571-0653(05)80034-4 |
| Popis: | In this extended abstract we describe a computational study to solve hard frequency assignment problems (FAPs) to optimality using a tree decomposition of the graph that models interference constraints. We present a dynamic programming algorithm which solves FAPs based on this tree decomposition. With the use of several dominance and bounding techniques it is possible to solve small and medium-size real-life instances of the frequency assignment problem to optimality. Moreover, with an iterative version of the algorithm we obtain good lower bounds for large-size instances within reasonable time and memory limits. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect