Frage: In der Vorlesung EAKT mit Schwerpunkt
KT(Wintersemester 2004)
wurde ein einfacherer PTAS für das Makespan Scheduling
Problem vorgestellt auf 2 Maschinen. Verallgemeinert sich
der dort beschriebene Algorithmus nicht auch einfach zu einem PTAS
auf m>2 Maschinen?
(Frage ist wohl nur für diejenigen
interessant, die die Vorlesung damals gehört haben.)
Antwort: Nein! Man kann zwar den Algorithmus für m>2
verallgemeinern, er hat dann auch Laufzeit m hoch (1/epsilon)
statt 2 hoch (1/epsilon) wie im Fall m=2.
Aber: Die Approximationsgüte ist nicht mehr 1+epsilon oder
1+2epsilon, sondern viel schlechter, eher so etwas wie 1+m*epsilon
oder 1+m*epsilon/2. Würde man nun wieder das epsilon anpassen, so
würde die Laufzeit in Abhängigkeit von m nach oben gehen....!
Frage:Beim Beweis der Güte 1+ln n beim Set-Cover-Algorithmus
hast Du an einer Stelle das Schubfachprinzip zur Anwendung gebracht.
Kannst Du genauer erklären, wie das dort zur Anwendung kam?
Antwort: Ja. Ich habe nun im aktualisierten Skript
einen Anhang hinzugefügt, der das Schubfachprinzip noch einmal
explizit auflistet und im Beweis für die Güte die
Referenz auf den Satz aus dem Anhang explizit angegeben.