- ...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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
