Direkt zum Inhalt | Direkt zur Navigation

Benutzerspezifische Werkzeuge

Sektionen

Footnotes

...Raumzeit
nicht physikalisch zu verstehen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...ILP
Ganzzahliges (integer) lineares Programm: Wenn nicht anders angegeben, sind stets alle Variablen aus 11#11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...sind.
Tatsächlich besteht nach eigener Erfahrung ein großer Unterschied darin, ob er die betroffenen Personen kennt, oder mit einem anonymisierten Plan arbeitet.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Listengröße
wobei alle Knoten Listen der gleichen Größe erhalten
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...läßt
Die Möglichkeit der Garantie einer konstanten Zahl kann man ausschließen, indem man den Graphen mehrfach reproduziert.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...([Tuz97],[dW95])
Eine analoge Konstruktion läßt sich im Bereich der Listenfärbbarkeit einsetzen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...ist
MIS im komplementären Graphen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...ist.
Für dieses Beispiel danke ich Dr. Vygen vom Institut für Diskrete Mathematik.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...zeigt
Sofern der Graph nicht vollständig oder ein Kreis ungerader Länge ist.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Abschnitt
ohne Hinzunahme relativer Bedingungen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...werden.
Zumindest kann sie nicht fallen, da die Problemmenge stets erweitert wird.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Farbklassen
Was mittels eines Greedy-Algorithmus stets mit 60#60 Farben möglich ist.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Nichtexistenz
82#82 vorausgesetzt
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...(b)
Sind die Graphen zwischen den Ebenen vollständig, geht b) in a) über.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...schwer.
Im Gegensatz zu Max2SAT, das konstant approximierbar ist.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Problem
TSP mit mehreren Händlern
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...liegt.
In einigen Randgebieten allerdings sind zur Berechnung der Qualität selbst z.B. Simulationen erforderlich [MR98].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Netzwerk
ggf. mit Kapazitäten, Anforderungen und Kosten
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...teilen.
Interessanterweise wird deren 1#1-Vollständigkeit erstmals im selben Paper gezeigt, wie die des Timetabling[EIS76], ohne daß dabei auf die Reduktion eingegangen wird.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...kann.
Es ist kein Problem, daß Fluß 1 Kanten von Fluß 2 benutzen kann, da er auf diese Weise nur Kanten erreicht, die auf kürzerem Wege von seiner Quelle aus ohnehin erreicht werden und Kapazität 1 haben.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...stellt.
Erstaunlicherweise scheint dieser Satz im Timetabling-Bereich noch keine Beachtung gefunden zu haben, vgl. z.B. [dW96].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...154#154[Blu98]
Im gradbeschränkten Fall läßt sich dies laut [CL92] auf 155#155 verbessern.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...symmetrischer
Notwendig, damit die Menge konvex bleibt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...gilt.
Obwohl der Schluß zwischen Vorzeichen der Teildeterminanten auf die Determiniertheit i.a. nur für positive Determiniertheit gilt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Intervallarithmetik[SM97]
Oder auch durch Resolution; dann wird das Ganze als Logisches Verfahren bezeichnet.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...sind.
Damit wird genau das Problem betrachtet, das EVEN et al. [EIS76] 13 Jahre später als 1#1-hart beweist.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...akzeptiert
Beim Minimierungsproblem.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...[HHW96].
Mit dem Begriff Phase Transition wird häufig auch ein entsprechender Übergangsbereich bei Problemklassen assoziiert, was auch so interpretiert werden kann, daß mit wechselnder Temperatur das Problem die Klassen wechselt [Cor97].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...werden,
In der Topologie gibt es ein Buch, daß zwar keine Fehlschläge, aber immerhin die entsprechenden Gegenbeispiele aufzählt [SS78].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...[Dou95]
Total unimodulare Graphen sind auch unimodular.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...lösen
Was nicht die Lösbarkeit von 236#236 impliziert.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...dar
Sind bei Indizierungen weniger Indizes angegeben als in der Definition (*), ist der Vektor gemeint, der entsteht, wenn man alle Werte des entprechenden Parameters einsetzt. Auf Vektoren bezogen sind die Relationszeichen stets komponentenweise zu verstehen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Zwischenablage
Copy-Puffer\
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...darstellt.
In [Laj95] wurde mit Speicheranforderungen im Gigabyte - Bereich gearbeitet, um ein größeres Problem der automatischen Stundenplanerstellung zu behandeln.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...dicht
In Anlehnung daran, aber nicht im eigentlichen mathematischen Sinne.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...aufweisen.
In Betriebssystem-Terminologie: Es tritt keine Starvation auf.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...verwenden
Und das Ganze damit als Flußproblem auffassen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...revidiert.
Diese Möglichkeit scheint von den Befürwortern dieser Methode vollkommen ignoriert zu werden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...k-Opt
k-Opt ist ein beim TSP häufig angewendetes Optimierungsverfahren. [Jun90]
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...size=-1>ALE
Wobei mir nicht bekannt ist, ob es eine Anwendbarkeit in der Matchingtheorie gibt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...auf
Bzw. es tritt nur dann auf, wenn man es explizit vorsieht.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...werden.
Die Zahl der Händler bei [BHM96] liegt in der Größenordnung von 30.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...wurde
Visual C++ bietet ein ähnliches Konstrukt an, warnt aber, daß dieses sehr viele Kopieroperationen benötige.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Bildlauf-Funktion
Scrolling
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...werden
Und keine Mengen als Elemente anderer Mengen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...werden,
Durch Klick mit der rechten Maustaste wird automatisch der oberste Ablageneintrag eingefügt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...ist.
MIMOSA [Mim98] bietet 1000 Schritte an, aber sowohl dies als auch eine dynamische Implementierung, die beliebig viele Schritte unterstützen könnte, erschienen übertrieben.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...gelöscht.
Das Funktionieren dieses Features konnte nur im Debugger beobachtet werden. Es gibt keinen für den Benutzer transparenten Test, der dies später verifizieren könnte.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...zugeteilt.
Es wird kein Versuch unternommen, etwaige fehlende Objekte zu ergänzen, da durch deren Hinzufügen zumeist der Bezug zu einer Voraussetzungs-Gruppe verloren würde.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...werden.
Siehe auch [CK95b].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Stundenplanerstellung
z.B. Mimosa [Mim98]
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Test-Version
Visual C++ bietet hier eine Trennung an.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...5.0
©Microsoft
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Praktikum
Cremers,Karpinski: Effiziente Algorithmen für kombinatorische Optimierungsprobleme; SS1997
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Nichtapproximierbarkeit
Vorausgesetzt 82#82.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Tabellenformen
Die es in den meisten Datenbankprogrammen nicht gibt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

(c) Martin Loehnertz 1999