Prof. Dr. Ir. Arie M.C.A. Koster
general / CV / research / publications / teaching / supervision / resources /
- subpages:
- PhD thesis / DualNet /
- Frequency Assignment - Models and Algorithms
-
Frequentie Toewijzing - Modellen en Algoritmen
Arie M.C.A. Koster
Proefschrift Universiteit Maastricht, Maastricht, Nederland, 1999.
Ph.D. thesis Universiteit Maastricht, Maastricht, The Netherlands, 1999
ISBN 90-9013119-1Available in pdf-format. The accompanying "stellingen" (theses, in Dutch) are also available. For hardcopies, please mail to koster@math2.rwth-aachen.de
Contents
- Preface
- Contents
- List of Figures
- List of Tables
- Introduction
- History of Wireless Communication
- Applications of Wireless Communication
- Radio and television broadcasting
- Terrestrial mobile cellular networks
- Satellite-based cellular systems
- Fixed cellular telecommunication networks
- Outline of this thesis
- The Frequency Assignment Problem: A Survey
- The Frequency Assignment Problem
- Fixed Channel Assignment
- Minimization of the Maximum Penalty
- Minimization of the Cumulative Penalty
- Frequency Assignment and Graph Coloring
- Application specific properties
- Minimum Order Frequency Assignment
- Problem Definition
- Benchmark Instances
- Lower Bounds and Exact Methods
- Heuristics
- Conclusions
- Minimum Span Frequency Assignment
- Problem Definition
- Benchmark Instances
- Lower Bounds and Exact Methods
- Heuristics
- Conclusions
- Minimum Blocking Frequency Assignment
- Problem Definition
- Lower Bounds and Exact Methods
- Heuristics
- Conclusions
- Minimum Interference Frequency Assignment
- Problem Definition
- Benchmark Instances
- Lower Bounds and Exact Methods
- Heuristics
- Conclusions
- Other Models
- Conclusions
- The Partial Constraint Satisfaction Formulation
- The partial constraint satisfaction problem
- Formulation, Dimension and Trivial Facets
- Lifting theorems
- Non-trivial classes of facets
- The cycle inequalities
- The clique-cycle inequalities
- Separation of non-trivial facets
- The cycle inequalities
- The clique-cycle inequalities
- The Boolean Quadric Polytope and the PCSP
- Computational Results
- Concluding Remarks
- A Tree Decomposition Approach
- Graph Theoretic Concepts
- Construction of a Tree-Decomposition
- Minimum separating vertex set in a graph
- Heuristic
- Dynamic Programming Algorithm
- Reduction Techniques
- Constraint graph reduction
- Penalty shifting - Lower bounding
- Domain reduction
- Upper bounding
- Dominance
- Iterative Version Algorithm
- Computational Results
- Preprocessing
- Construction of Tree-decompositions
- Dynamic Programming Algorithm
- Iterative version
- Iterative Algorithm and Integer Programming
- Concluding Remarks
- Local Search Approaches
- Preliminaries
- Local Search and Integer Programming
- Neighborhood
- Computational Results
- Local Search and Tree Decomposition
- Neighborhood
- Computational Results
- Concluding Remarks
- Directions for Further Research and Concluding Remarks
- Directions for Further Research
- Benders Decomposition
- Lagrangean Relaxation
- Semi-Definite Programming Relaxation
- Frequency Assignment Formulation
- Conclusions
- Bibliography
- Author index
- Samenvatting in het Nederlands - Summary in Dutch
- Introductie
- Frequentie Toewijzing: Een Overzicht
- Exacte Methoden voor het MI-FAP
- Heuristieken voor MI-FAP
- Richtingen voor Nader Onderzoek en Conclusies
- Curriculum Vitae
last modified: 23/08/2018 - 09:43