Show description

Nicht zu zeigen braucht man, daB der Algorithmus sich unabhangig von der Auswahl schlecht verhalt. Wenden wir uns wieder dem Algorithmus zu. Der Grad eines Graphen G kann von der Anzahl ^ = |F| der Knoten abhangen, er kann sogar 0(^) sein. In diesem Fall ist die absolute Abweichung von GREEDYCOL sehr groB, er kann Ergebnisse liefem, deren Wert sehr weit vom Wert der optimalen Losung entfemt ist. 2 ab Seite 46 stellen wir einen weiteren sehr einfachen greedy Algorithmus vor, der mit 0{n/\ogn) Farben auskommt.

Der Einfachheit halber nehmen wir an, daB die Objekte schon nach ihrem Volumen sortiert vorliegen, d. h. ^1 < • • •

9) einen Algorithmus, der als Eingabe eine Beschreibung von G bekommt und als Ausgabe eine Kanten-(A(G) + 1)-Farbung von G berechnet. Bestimme die Laufzeit des Algorithmus. 9) eine Kanten-(A(G) + 1)-Farbung berechnen kann. Mit anderen Worten: Gib einen 1-Zeugen gegen FARBEKANTEN an. 10 Beim Problem Max-2BlNPACKlNG ist eine Probleminstanz / gegeben durch eine Menge S von n Objekten der Volumina 5'i,... ,5'„ G IN und zwei Kisten (engl: bins) mit Fassungsvermogen jeweils C G IN. Eine zulassige Losung L = [-5*1,/S'2] besteht aus zwei disjunkten Teilmengen S\, S2 von S, so daB das Volumen von S\ und das von S2 jeweils hochstens C ist, also die beiden Mengen in je eine Kiste gepackt werden konnen.