Mit diesem einfachen Verfahren lässt sich bereits eine gute Lösungsqualität erreichen; die (asymptotische) Abweichung vom Optimum beträgt höchstens etwa 22% (genauer gesagt ist die absolute Abweichung vom Optimum p_M(S) nie mehr als 2/9 × p_M(S) + 4).

Der Zusammenhang mit dem DAB-Blockzuweisungsproblem ist relativ offensichtlich; man setze „Gegenstände“ = „Dienste“ und „Behälter“ = „DAB-Blöcke“. Tatsächlich entspricht die Packungszahl p_M(S) der Minimalzahl von Frequenzen, die zur Versorgung eines einzelnen Gebiets mit Versorgungsanforderung S benötigt werden. Es liegt daher auf der Hand, Packungsalgorithmen für die erste Stufe des DAB-Blockzuweisungsproblems anzuwenden. Zwei einfache Verfahren, die bereits relativ gute Ergebnisse liefern (vgl. Abschnitt 4.5) sind die Folgenden:

SFF(„Simultaneous First Fit“): Man wende den FFD-Algorithmus einzeln auf alle angeforderten Dienstemengen R_v an. Dies ergibt offenbar eine strikte Blockzuweisung, d. h., eine Blockzuweisung, die alle Anforderungen genau erfüllt.

GFF(„Global First Fit“): Man wende den FFD-Algorithmus auf die Gesamtmenge aller angeforderten Dienste S = _vV R_v an. Danach weise man jeden Block B genau den Gebieten v zu, deren Versorgungsanforderung einen Dienst aus B enthält. Auf diese Weise erhält man eine überlappungsfreie Blockzuweisung, d. h., die Blöcke sind paarweise disjunkt.

Färben der DAB-Blöcke Ist erst einmal eine Blockzuweisung errechnet, so muss man noch eine zugehörige Kanalzuweisung finden, wobei die oben angeführten Interferenzfreiheitsbedingungen eingehalten werden müssen. Der Zusammenhang dieses Teilproblems mit dem Graphfärbungsproblem wird über den sogenannten Blockgraphen hergestellt, der sich aus einer Blockzuweisung B wie folgt ergibt:

• die Knoten des Blockgraphen sind die Knoten-Block-Paare (v,B), für die B B_v;
• die Kanten des Blockgraphen bezeichnen genau die Paare von Knoten-Block-Paaren, die durch verschiedene Kanäle vor Interferenzen geschützt werden müssen, d. h. jene Paare (v,B)(w,C), für die BC und entweder v = w oder vw E.

Wie man leicht sieht, ist dann eine zulässige Kanalzuweisung für die gegebene Blockzuweisung identisch mit einer Färbung des entsprechenden Blockgraphen.

4.4.  Kontrolle der Lösungsgüte

Wie beim „einfachen“ Kanalzuweisungsproblem, d. h. dem Graphfärbungsproblem, ist man natürlich auch beim DAB-Blockzuweisungsproblem an unteren Schranken interessiert, die eine Kontrolle der Güte der mit den Planungsheuristiken errechneten Blockzuweisungen gestatten. Die Cliquezahl des Gebiets-Kopplungsgraphen selbst ist hier wenig nützlich, da zusätzlich die Versorgungsanforderungen berücksichtigt werden müssen. Der Schlüssel zur Lösung dieses Problems liegt auch hier