Aller au contenu. | Aller à la navigation

Outils personnels

Navigation

Approximierbarkeit

next up previous contents
Next: Randomisierte Algorithmen/Heuristiken Up: Komplexität des Problems Previous: Realistische Problemstellungen sind -vollständig

Approximierbarkeit

  

Fälle mit unbeschränktem Grad

Minimierung der Zeitstundenzahl
Bei zahlreichen tex2html_wrap_inline5146 -vollständigen Problemen kann sowohl die Approximation bis auf konstante Abweichung, als auch bis auf einen gewissen konstanten Faktor als ebenfalls tex2html_wrap_inline5146 -vollständig nachgewiesen werden. Es zeigt sich, daß bei uneingeschränkten Formen von Prüfungsverteilungen und beim University-Timetabling noch wesentlich schlechtere Verhältnisse vorliegen, da das Problem des Graphenfärbens darauf L-reduziert werden kann.

Def743

Das heißt, wenn es einen Approximationsalgorithmus für B gibt, gibt es auch einen für A, wobei dieser höchstens um einen konstanten Faktor schlechter ist. Im folgenden soll gezeigt werden, daß - wenn man keine speziellen Voraussetzungen anwendet - ein approximativer Algorithmus für das Timetabling-Problem verwendet werden könnte, um das Färben eines Graphen zu approximieren.

Satz752

Bem756

In [Hal93] wird - allerdings basierend auf anderen Voraussetzungen - die Vermutung geäußert, daß keine bessere Approximation als tex2html_wrap_inline5368 für ein festes c möglich ist. Die Reduktionen auf die beiden genannten TimetablingProbleme erweisen sich als triviale Umformungen, die, da jeweils eins zu eins Beziehungen zwischen den zu färbenden Objekten bestehen, offensichtlich L-Reduktionen sind: Für jeden Knoten wird ein Termin vorgesehen und für jede Kante eine Person, die an beiden Terminen teilnimmt.

Es kann natürlich dennoch approximative Algorithmen für bestimmte Spezialfälle geben. Die Anforderungen an einen solchen wären relativ zu der obigen Aussage aber recht hoch, da z.B. herkömmliche Schul-Stundenpläne bei 40 zur Verfügung stehenden Wochenstunden Klassen bis zu 30 Unterrichtsstunden in der Woche haben können, so daß mit tex2html_wrap_inline5372 mindestens ein tex2html_wrap_inline5374 - Approximationsalgorithmus gefunden werden müßte, wobei es unwahrscheinlich ist, daß tatsächlich eine Färbung mit 30 Farben existiert.

Vorgegebene Zeitstundenzahl
Man kann die Anforderung an einen Timetabling-Algorithmus also zu präzisieren versuchen und fragen, ob es einen Algorithmus gibt, der, gegeben eine Zahl k von Farben, einen Graphen mit diesen färbt und nur einen konstanten Anteil der Knoten ungefärbt läßtgif. Aber auch hierfür ergibt sich, daß der allgemeine Fall unlösbar ist:

Lem770

Beweis:
Man wendet den Algorithmus mit stets neuen k Farben iteriert auf die jeweils noch nicht gefärbten Knoten an. Dies muß man höchstens tex2html_wrap_inline5392 mal anwenden, bis weniger als 1 Knoten übrig ist.

Für jedes tex2html_wrap_inline5396 gibt es aber ein tex2html_wrap_inline5398 , so daß tex2html_wrap_inline5400 ist wobei anzumerken ist, daß es zu jedem k beliebig große Graphen G mit tex2html_wrap_inline5406 gibt.

Um diesen Fall zu betrachten, kann des weiteren folgende Konstruktion herangezogen werden ([Tuz97],[dW95])gif: Jeder Knoten des Graphen werde durch eine Clique der Größe k ersetzt, wobei mit jedem Knoten der Clique eine Farbe assoziiert wird. Die neuen Knoten seien jeweils durch das Paar aus alter Knotenbezeichnung und Farbe markiert. Dann verbindet man alle Knoten gleicher assoziierter Farbe miteinander, deren Originale im Ausgangsgraphen verbunden waren. Die Kantenmenge des neuen Graphen ergäbe sich somit also als

displaymath5410

Offenbar korrespondiert eine unabhängige Menge im neuen Graphen zu einer korrekten, aber nicht notwendig vollständigen Färbung des alten, wenn man ein Element dieser Menge so interpretiert, daß der Originalknoten eines ausgewählten Knotens die diesem assoziierte Farbe erhält. Die Wohldefiniertheit wird hierbei durch die Cliquen und die Korrektheit durch die übrigen Kanten gewährleistet.
Diese Konstruktion erlaubt es zudem, einige relative Nebenbedingungen zu modellieren, da man nun dafür sorgen kann, daß Zuordnungen einander ausschließen. So z.B. kann man jede Kombination (s,x), bei der s eine Schwimmstunde für die entsprechende Klasse darstellt, mit allen Stunden (p,y) verbinden, bei denen p eine Mathematikstunde derselben Klasse und y eine Stunde ist, die am selben Tag aber später als x liegt. Damit wäre dann sichergestellt, daß niemals Mathematik auf Schwimmen folgen kann.
Umgekehrt kann man natürlich das Problem der maximalen unabhängigen Teilmenge (MIS) als das Problem ansehen, einen Graphen mit k=1 Farbe so zu färben, daß möglichst wenige Knoten übrigbleiben. [Hoc97] folgend ist dieses Problem im nicht gradbeschränkten Fall konsistent damit genauso hart wie das des Graphenfärbens, da auch für das MIS eine untere Approximierbarkeitsschranke des selben Typs angegeben werden kann [Has96].
Ein Vorteil, den man gegenüber dem allgemeinen Graphenfärbungsproblem hat, ist, daß, da der Graph aus einem anderen Problem konstruiert wurde, die Cliquenzahl bekannt ist, deren Ermittlung normalerweise ebenfalls hart istgif. Hieraus läßt sich aber für einen exakten Algorithmus anscheinend kein Vorteil gewinnen, da, obwohl z.B. in einem planaren Graphen alle Cliquen in tex2html_wrap_inline5426 aufgezählt werden können, die Entscheidung ob dieser 3- oder 4-färbbar ist, tex2html_wrap_inline5146 -vollständig ist.gif Ob dies die Approximation erleichtert, scheint bisher noch nicht untersucht worden zu sein. Zudem ist mit der Lovaszschen tex2html_wrap_inline5434 -Funktion [Knu94] stets ein Wert bekannt, der zwischen chromatischer Zahl und Cliquenzahl liegt, so daß somit eine bessere untere Schranke für tex2html_wrap_inline5436 immer gegeben ist.

Insgesamt läßt sich also sagen, daß das Problem, wenn man keine Anforderungen an die Größe der Differenzierungen stellt, nicht mit konstanter Qualität approximierbar ist.

Beschränkter Grad

Minimierung der Zeitstundenzahl
Für den Fall, daß man die Größe der Differenzierungsgruppen als beschränkt annimmt, funktioniert die obige Reduktion des Knotenfärbens nicht mehr, da das Timetablingdann zu Fällen mit begrenztem Knotengrad korrespondiert. Die umgekehrte Transformation ist natürlich auch möglich, was dazu führt, daß der Satz von Brooks, der tex2html_wrap_inline5438 zeigtgif [Die96], anwendbar wird. Dies liefert aber dennoch keinen Algorithmus für die automatische Stundenplanerstellung, da der Knotengrad hier im Schnitt ca. dreimal größer ist, als die angestrebte Farbenzahl. Selbst dann wäre er nur um 1 besser, als die von jedem Greedy-Algorithmus garantierbare Schranke von tex2html_wrap_inline5442 .
Relaxiert man die Ansprüche weiter und verlangt, daß nur ein bestimmter Anteil der Kanten beide Enden in der jeweils gleichen Farbklasse hat, so gelangt man zum Begriff der sogenannten Semifärbungen, wobei bei diesen ein Fehleranteil von maximal tex2html_wrap_inline5444 vorgesehen ist. Hier läßt sich mit hoher Wahrscheinlichkeit und unter Einsatz semidefiniter Programmierung eine Semi-Färbung mit tex2html_wrap_inline5446 Farben erzielen [Hoc97], was selbst, wenn man als Konstante nur 1 zuläßt, mit tex2html_wrap_inline5450 und k=30 zu einer Farbenzahl von 52 führen würde, wobei wegen der relativ großen Zahl von Kanten noch immer jeder Knoten mit einer ungültigen Kante inzident sein könnte. Nach dem Schubfachprinzip müßte, um einen Anteil von p gesetzten Stunden zu garantieren, die Approximationsgüte bezüglich der Kanten tex2html_wrap_inline5458 tex2html_wrap_inline5460 tex2html_wrap_inline5462 betragen.

Vorgegebene Zeitstundenzahl
Wählt man die selbe Reduktion auf das MIS-Problem wie im letzten Abschnittgif, so liegt auch hier der Fall mit beschränktem Grad vor, da die Größe jeder Clique durch k und die Zahl der übrigen Kanten durch den (beschränkten) Grad des Originalknotens gegeben ist. Für Graphen mit tex2html_wrap_inline5466 zeigen BERMAN und KARPINSKI [BK98], daß sich eine Approximationsgüte von tex2html_wrap_inline5468 nicht unterschreiten läßt. Dies wäre zwar noch hinreichend, aber die erreichbare Güte scheint mit wachsendem Grad strikt größer zu werden.gif
Betrachtet man die entsprechenden Approximationsversuche für das Problem der maximalen unabhängigen Knotenmenge in gradbeschränkten Graphen, so findet sich beispielsweise in [BF96] eine Approximationsgüte in der Größenordnung von tex2html_wrap_inline5470 , was in diesem Fall bedeuten würde, daß nur ca. tex2html_wrap_inline5472 der Knoten gefärbt würde ,wobei die hier eingesetzten Zahlwerte, die voraussetzen, daß es nur Differenzierungen der Größe 3 mit je 20 Stunden pro Objekt gibt, meiner Ansicht nach mehr als optimistisch sind. Durch die umgekehrte Reduktion und durch die Anwendung des Satzes von Brooks erhielte man tex2html_wrap_inline5478 . Unter der Voraussetzung, daß für den zu färbenden Graphen tex2html_wrap_inline5480 gilt, erhielte man durch iteriertes Färben mit tex2html_wrap_inline5436 Kanten also tex2html_wrap_inline5484 , was nur für tex2html_wrap_inline5486 zu weniger als 38 Farben führt.
Das Problem mit beschränktem Grad ist somit zwar konstant approximierbar, aber die Qualität ist für die praktische Anwendung nicht ausreichend. Polynomielle Approximationsschemata existieren für diesen Fall - zumindest in dieser Allgemeinheit - ebenfalls nicht, was diese Variante des Problems in die Komplexitätsklasse APX-PB, die laut [KMSV94] mit dem Abschluß der formalen Klasse MAX SNP übereinstimmt, einordnet.

Gewichtete Fälle

Da man stets eine Gewichtung mit den Werten tex2html_wrap_inline5178 wählen kann, sind die gewichteten Problemstellungen mindestens so schwer wie die ungewichteten. Über die exakte Komplexität und Approximierbarkeit des allgemeinen Falles gibt die Literatur soweit mir bekannt keinerlei Auskunft. Das Problem liegt natürlich in tex2html_wrap_inline5146 , da es möglich ist, all diese Kriterien in polynomieller Zeit zu überprüfen. Läßt man die die relativen Nebenbedingungen gänzlich außer Acht, so gelangt man zum GOCCP, über dessen allgemeine Approximierbarkeit nichts bekannt ist, das aber auf speziellen Graphenklassen gelöst werden kann (s. Abschnitt 4.10.1).
Verwendet man hier - eine vorgegebene Farbenzahl vorausgesetzt - erneut die obige Konstruktion zum Übergang auf das MIS-Problem an, so gibt es in [Hoc97] ein anwendbaren Approximationsalgorithmus, der eine minimale unabhängige Kantenmenge mit einem Gewicht findet, das vom optimalen nur um tex2html_wrap_inline5494 abweicht. Dieses Verfahren besteht im wesentlichen in der Ausnutzung einer vorangegangenen Zerlegung des Graphen in Farbklassengif. Könnte das obige Suchproblem besser gelöst werden und eine Färbung mit l Farben gefunden werden, so kann dies sogar auf tex2html_wrap_inline5500 verbessert werden, da man aus einer Färbung des Ausgangsgraphen stets eine Färbung des neuen (MIS-) Graphen erhalten kann, indem man l injektive Abbildungen tex2html_wrap_inline5504 mit tex2html_wrap_inline5506 tex2html_wrap_inline5508 wählt, was z.B. durch zyklisches Permutieren geht. Dann ordnet man dem Knoten (a,b) die Farbe tex2html_wrap_inline5512 zu. In praktischen Anwendungen ist es natürlich dennoch nicht sinnvoll, diese Färbung, die, wenn man die kleinsten l-k der Farbklassen als nichtgefärbt deklariert, immerhin tex2html_wrap_inline5516 approximativ war, zugunsten einer gewichteten tex2html_wrap_inline5500 -Approximation aufzugeben.


next up previous contents
Next: Randomisierte Algorithmen/Heuristiken Up: Komplexität des Problems Previous: Realistische Problemstellungen sind -vollständig

(c) Martin Loehnertz 1999