Warum ist komplementäre Schlaffheit wichtig?

Komplementäre Schlaffheit (CS) wird häufig gelehrt, wenn über Dualität gesprochen wird. Es stellt eine gute Beziehung zwischen der ursprünglichen und der doppelten Einschränkung / Variablen aus mathematischer Sicht her.

Die zwei Hauptgründe für die Anwendung von CS (wie in Kursen und Lehrbüchern für Hochschulabsolventen gelehrt):

Um die Optimalität der LP zu überprüfen
Um das Dual zu lösen

Ist CS angesichts der heutigen Rechenleistung und der Polynomalgorithmen zur Lösung von LPs aus pragmatischer Sicht immer noch relevant? Wir könnten immer nur die Duals lösen und beide oben genannten Punkte ansprechen. Ich stimme zu, dass es "effizienter" ist, das Dual mit Hilfe von CS zu lösen, aber ist es das? Oder gibt es bei CS mehr, als man denkt? Wo genau ist CS über die beiden oben genannten Punkte hinaus nützlich ? Ich habe häufig Texte gesehen, die auf das Konzept von CS anspielen, wenn ich über Approximationsalgorithmen spreche, aber ich verstehe seine Rolle dort nicht.

ds.algorithms approximation-algorithms linear-programming primal-dual PhD
quelle

Nicht mein Fachgebiet, aber es hört sich so an, als würden Sie sich fragen, warum wir Eigenschaften von X vermitteln, obwohl die Entscheidung für X rechnerisch einfach ist. Warum lehren wir beispielsweise die Charakterisierung der Zweigliedrigkeit "keine ungeraden Zyklen = zweiteilig", obwohl wir polynomielle Zeitalgorithmen zur Überprüfung der Zweigliedrigkeit haben? Fragen Sie das in gewissem Sinne?

Robin Kothari

Nicht genau. Ich verstehe "warum" du es unterrichtest. Ich möchte aus einem praktischen POV wissen, wie es beim Lösen von LPs und / oder beim Entwerfen von Approximationsalgorithmen verwendet wird. Welche Erkenntnisse erhalten wir außer den mathematischen Beziehungen zwischen den Variablen und den Einschränkungen?

PhD

Nun, ich denke, es kann helfen, "analytische" Lösungen zu erhalten ... die mit einem Computer möglicherweise schwieriger zu bekommen sind.

Usul

Ich "verstehe" die Frage nicht. Nur weil wir Taschenrechner und Computer verwenden, um Zahlen zu addieren und zu multiplizieren, müssen wir noch die Eigenschaften von Zahlen kennen?

Chandra Chekuri

@ChandraChekuri - das meine ich nicht. Ich versuche nur herauszufinden, was an diesem Theorem so großartig ist und was es wichtig macht. Ich möchte es nicht als "so ist es" akzeptieren, möchte aber ein tieferes Verständnis seiner Bedeutung für die LP-Dualität haben

PhD

Komplementäre Schlaffheit ist der Schlüssel zum Entwerfen von Primal-Dual-Algorithmen. Die Grundidee ist:

$y$
$x$ $(x, y)$
$x$ $y$

$s$ $t$ $s$ $t$

Primal-Dual-Algorithmen sind aus vielen Gründen hilfreich. Philosophisch bieten sie mehr Einblick als ein generischer Algorithmus. Sie geben normalerweise stark polynomielle Zeitalgorithmen an, während wir immer noch keine stark polynomiellen LP-Löser haben. Sie sind oft praktischer als generische Algorithmen. Dies gilt insbesondere dann, wenn wir die LP nicht explizit aufschreiben können und unsere einzige andere Wahl der Ellipsoid-Algorithmus ist, was beim nicht-zweigliedrigen Matching und beim Primal-Dual-Algorithmus von Edmonds der Fall ist.

$y$ $x$ $y$ $x_i > 0$ $y_j > 0$ $x$ $\alpha$ $\alpha$

Sasho Nikolov
quelle

Warum ist komplementäre Schlaffheit wichtig?

Antworten: