Minimale maximale Lösungen von LPs

Die lineare Programmierung ist heutzutage natürlich sehr gut bekannt. Wir haben viel Arbeit, die die Struktur machbarer Lösungen und die Struktur optimaler Lösungen charakterisiert. Wir haben die starke Dualität, Poly-Time-Algorithmen usw.

Aber was ist über minimale Maximallösungen von LPs bekannt? Oder gleichermaßen Maximum-Minimum-Lösungen?

(Dies ist eigentlich keine Forschungsfrage, aber vielleicht können wir etwas weniger technisches für die Feiertage haben. Ich bin nur neugierig und nach einigem googeln habe ich das Gefühl, dass ich die richtigen Schlüsselwörter vermissen muss. Es fühlt sich an wie eine Selbstverständlichkeit Problem zu studieren, aber ich fand nur einige sporadische Papiere, die das Problem erwähnen.)

Konzentrieren wir uns zur Vereinfachung auf das Verpacken und Abdecken von LPs . In einer Verpackung LP werden wir eine gegebenen nicht-negative Matrix . Ein Vektor ist möglich, wenn und . Wir sagen , dass ist maximal , wenn es möglich ist , und wir können jede Komponente nicht gierig erhöhen. Das heißt, wenn und , dann ist nicht durchführbar. Und schließlich ist a $A$ $x$ $x \ge 0$ $Ax \le 1$ $x$ $y \ge 0$ $y \ne 0$ $x + y$ $x$ minimale maximale Lösung, wenn sie die Zielfunktion unter allen maximalen Lösungen minimiert . $\sum_i x_i$

( In analoger Weise können Sie eine Maximum-Minimum- Lösung einer Covering-LP definieren .)

Wie sieht der Raum minimaler maximaler Lösungen aus? Wie können wir solche Lösungen finden? Wie schwierig ist es, solche Lösungen zu finden? Wie können wir solche Lösungen approximieren? Wer studiert solche Dinge und wie lautet der richtige Begriff dafür?

Diese Fragen wurden ursprünglich durch randdominierende Mengen und minimale maximale Übereinstimmungen motiviert . Es ist bekannt (und ziemlich leicht zu erkennen), dass eine minimale maximale Übereinstimmung eine minimale kantenbeherrschende Menge ist; Umgekehrt ist es bei einer minimalen kantenbeherrschenden Menge einfach, eine minimale maximale Übereinstimmung zu konstruieren.

Sie sind also im Wesentlichen das gleiche Problem. Beide Probleme sind NP-hart und APX-hart. Es gibt einen trivialen 2-Approximationsalgorithmus: jede maximale Übereinstimmung.

Ihre "natürlichen" LP-Relaxationen sehen jedoch sehr unterschiedlich aus. Wenn Sie das kantenbeherrschende Set-Problem annehmen und eine natürliche LP-Entspannung bilden, erhalten Sie eine Cover-LP. Was bekommen Sie jedoch, wenn Sie das Problem haben, ein Minimum-Maximum-Matching zu finden und versuchen, eine LP-Entspannung zu finden? Natürlich sind fraktionierte Übereinstimmungen mögliche Lösungen für eine Packungs-LP. dann sind maximale fraktionale Übereinstimmungen maximale Lösungen solcher LPs, und minimale maximale fraktionale Übereinstimmungen sind daher minimale maximale Lösungen solcher LPs. :)

cc.complexity-theory ds.algorithms reference-request linear-programming optimization Jukka Suomela
quelle

Ihre Definition von maximal als "wir können keine Komponente gierig erhöhen" klingt sehr nach Nash Equilibrium. Gibt es hier eine versteckte Verbindung zur Spieltheorie?

Derrick Stolee

Ist es nicht so, dass für jede maximale Lösung

im LP-Packungsbeispiel

? Dann suchen wir im Wesentlichen nach einer minimalen (in

-Norm) Lösung des linearen Gleichungssystems.

x^{'}

$x'$

A x^{'} = 1

$Ax'=1$

L_{\infty}

$L_{\infty}$

Imran Rauf

A x = 1

$Ax = 1$ .

Jukka Suomela

Kennen Sie sich mit engpasslinearen Programmen aus , bei denen der Minimax-Aspekt ausschließlich in der Zielfunktion liegt?

Mike Spivey

Maximalität und Minimalität: Sie sind Arten von Pareto-Optimalität.
Komplexität: Ich denke, eine minimale maximale Lösung zu finden ist NP-schwer. Ich würde das Problem der Unabhängigkeitsdominierung (auch bekannt als das Minimum Maximum Independent Set Problem) in zweigeteilten Graphen reduzieren. Es ist bekannt, dass dieses Problem (genauer gesagt seine Entscheidungsversion) NP-vollständig ist (DG Corneil und Y. Perl, Clustering and Domination in perfect graphs. Discrete Applied Mathematics 9 (1984) 27-39). Da ein zweigliedriger Graph perfekt ist, wird sein unabhängiges festgelegtes Polytop durch die Cliquen-Ungleichungen bestimmt, und die Anzahl der Cliquen in einem zweigliedrigen Graph ist polynomiell. Daher können wir ein System linearer Ungleichungen Ax <= 1, x> = 0 für das unabhängige Mengenpolytop explizit aufschreiben. Die Extremlösungen entsprechen den unabhängigen Mengen, und die Extremmaximallösungen entsprechen den maximalen unabhängigen Mengen.

Yoshio Okamoto
quelle

Minimale maximale Lösungen von LPs

Antworten: