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-1

Available in pdf-format. The accompanying "stellingen" (theses, in Dutch) are also available. For hardcopies, please mail to kosterzib.de

The cover of my Ph.D. thesis

Contents

  1. Introduction
    1. History of Wireless Communication
    2. Applications of Wireless Communication
      1. Radio and television broadcasting
      2. Terrestrial mobile cellular networks
      3. Satellite-based cellular systems
      4. Fixed cellular telecommunication networks
    3. Outline of this thesis
  2. The Frequency Assignment Problem: A Survey
    1. The Frequency Assignment Problem
    2. Fixed Channel Assignment
      1. Minimization of the Maximum Penalty
      2. Minimization of the Cumulative Penalty
      3. Frequency Assignment and Graph Coloring
      4. Application specific properties
    3. Minimum Order Frequency Assignment
      1. Problem Definition
      2. Benchmark Instances
      3. Lower Bounds and Exact Methods
      4. Heuristics
      5. Conclusions
    4. Minimum Span Frequency Assignment
      1. Problem Definition
      2. Benchmark Instances
      3. Lower Bounds and Exact Methods
      4. Heuristics
      5. Conclusions
    5. Minimum Blocking Frequency Assignment
      1. Problem Definition
      2. Lower Bounds and Exact Methods
      3. Heuristics
      4. Conclusions
    6. Minimum Interference Frequency Assignment
      1. Problem Definition
      2. Benchmark Instances
      3. Lower Bounds and Exact Methods
      4. Heuristics
      5. Conclusions
    7. Other Models
    8. Conclusions
  3. The Partial Constraint Satisfaction Formulation
    1. The partial constraint satisfaction problem
    2. Formulation, Dimension and Trivial Facets
    3. Lifting theorems
    4. Non-trivial classes of facets
      1. The cycle inequalities
      2. The clique-cycle inequalities
    5. Separation of non-trivial facets
      1. The cycle inequalities
      2. The clique-cycle inequalities
    6. The Boolean Quadric Polytope and the PCSP
    7. Computational Results
    8. Concluding Remarks
  4. A Tree Decomposition Approach
    1. Graph Theoretic Concepts
    2. Construction of a Tree-Decomposition
      1. Minimum separating vertex set in a graph
      2. Heuristic
    3. Dynamic Programming Algorithm
    4. Reduction Techniques
      1. Constraint graph reduction
      2. Penalty shifting - Lower bounding
      3. Domain reduction
        1. Upper bounding
        2. Dominance
    5. Iterative Version Algorithm
    6. Computational Results
      1. Preprocessing
      2. Construction of Tree-decompositions
      3. Dynamic Programming Algorithm
      4. Iterative version
      5. Iterative Algorithm and Integer Programming
    7. Concluding Remarks
  5. Local Search Approaches
    1. Preliminaries
    2. Local Search and Integer Programming
      1. Neighborhood
      2. Computational Results
    3. Local Search and Tree Decomposition
      1. Neighborhood
      2. Computational Results
    4. Concluding Remarks
  6. Directions for Further Research and Concluding Remarks
    1. Directions for Further Research
      1. Benders Decomposition
      2. Lagrangean Relaxation
      3. Semi-Definite Programming Relaxation
      4. Frequency Assignment Formulation
    2. Conclusions
Last modified: Tue Feb 15 13:55:19 CET 2005 by Arie Koster