Die Zuteilung von Frequenzen an die Sender eines Netzes ist alles andere als einfach. Es muß jeweils das komplette Netz geplant werden, da Änderungen an einem Sender Auswirkungen im gesamten Netz haben können, die Randbedingungen sind sehr kompliziert, und die Zahl der zur Verfügung stehenden Kanäle ist gegenüber der Anzahl der Sender sehr gering. In Europa gibt es z.B. ca. 60.000 UKW-Sender, für die etwa 200 Kanäle zur Verfügung stehen.

Mathematisch gesehen kann das Problem als Graphfärbungsproblem modelliert werden. Vereinfacht gesprochen werden die Sender als Knoten eines Graphen dargestellt und genau dann mit einer Kante verbunden, wenn sie sich gegenseitig durch Interferenz o.a. stören können (Abbildung 3).

Es gilt nun, jedem Knoten eine Farbe (Kanal) so zuzuordnen, daß zwei mit einer Kante verbundene (sich also störende) Knoten unterschiedliche Farben (Kanäle) tragen.

Abbildung 3

Aus der Komplexitätstheorie ist bekannt, daß dieses Problem sehr schwierig ist (sog. NP-vollständig). Die Rechenzeit wächst exponentiell mit der Zahl der Sender, d.h. vergrößert man das Sendernetz nur um einen einzigen Sender, so verdoppelt sich die benötigte Rechenzeit für Frequenzzuweisung. Selbst schnellste Computer können hier keine Abhilfe schaffen. Benutzt man einen 1000 mal schnelleren Rechner, so kann man nur 10 Sender zusätzlich in der gleichen Rechenzeit planen.

Zur Lösung dieses Dilemmas bieten sich mehrere Wege an. Statt einer optimalen Lösung genügt für viele praktische Anwendungen eine, die nur näherungsweise das Optimum erreichen.

Für manche NP-vollständige Probleme gibt es Lösungen, die nur mit einer gewissen, aber sehr hohen Wahrscheinlichkeit das Optimum erreichen. Außerdem können