Techniken zum Nachweis von Grenzen der Integritätslücke in LP (SDP)

8

Ein Verweis auf Techniken zum Nachweis, dass die Größe einer Integritätslücke durch einen Ausdruck für eine bestimmte LP (oder SDP, aber weniger wichtig) begrenzt ist, ist erforderlich. Es wäre auch schön, einen Verweis auf einen Ort zu haben, an dem Techniken zur Minimierung von Integritätslücken beschrieben werden. Ich bin neu im Bereich der Integritätslücken, der ziemlich groß aussieht, daher ist die Beschreibung klassischer Ergebnisse der Beschreibung von etwas Heißem vorzuziehen.

ds.algorithms reference-request linear-programming semidefinite-programming integrality-gap Grigory Yaroslavtsev
quelle
Ihr Titel "Integritätslücken in LP (SDP)" ist zu allgemein, es ist besser, mit dem Titel Ihrer Frage genauer zu sein. Der Titel ist kein Tag, er sollte Ihre Frage enthalten, etwa: "Techniken zum Nachweis der Grenzen der Integritätslücke in LP (SDP)".
Kaveh

Antworten:

7

Betrachten Sie zur Diskussion das Minimierungsproblem mit der Zielfunktion . Ich kann mir keine dominante Technik zum Nachweis von Integritätslücken vorstellen. Normalerweise ist der Umriss des Beweises die Form, die durch die Definition der Integritätslücke impliziert wird, und die Details sind problemspezifisch.f(x)

Um zu zeigen, dass die Integritätslücke klein ist (dh LP ist gut), ist der folgende Beweisumriss üblich. Verwenden Sie eine Art Rundung (oft zufällig), um eine integrale Lösung mit für jedes LP-machbare (und für jede Probleminstanz ) zu konstruieren . Daraus folgt, dass die Integritätslücke höchstens beträgt . f ( x ' ) ≤ c ⋅ f ( x ) x Cx′f(x′)≤c⋅f(x)xc

Um zu zeigen, dass die Integritätslücke groß ist, ist der folgende Umriss üblich. Zeigen Sie eine Probleminstanz mit einer billigen LP-Machbarkeitslösung und beweisen Sie, dass es keine gute integrale Lösung gibt.

Warren Schudy
quelle
Sieht so aus, als sollte es , oder? f(x′)≤cf(x)
Grigory Yaroslavtsev
Vielen Dank, der Ansatz, den Sie beschrieben haben, um die Obergrenze für die Größe der Lücke zu beweisen, ist genau das, was ich tue. Die Konstruktion von ist in meinem Fall kein Problem, und dann muss ich die Ungleichung beweisen . Dies geschieht jetzt auf problemspezifische Weise, die sich kaum auf ähnliche Probleme derselben Klasse verallgemeinern lässt. Ich war also neugierig, ob es dafür eine allgemeine Maschinerie gibt. f ( x ' ) ≤ c f ( x )x′f(x′)≤cf(x)
Grigory Yaroslavtsev
@Grigory: Ich habe den Fehler behoben, den Sie in Bezug auf gemeldet haben und der . f ( x ' )x′f(x′)
Warren Schudy
Um Warrens Notizen zu ergänzen, gibt es zunehmend ausgefeilte (und sogar abhängige) Rundungsschemata und sogar Schemata zum Verpacken / Abdecken von Problemen, bei denen die Rundung die Machbarkeit auf schlechte Weise beeinträchtigen könnte. Je nachdem, um welches Problem es sich handelt, stehen erweiterte Referenzen zur Verfügung.
Suresh Venkat
8

Dies ist eine etwas schwere Maschinerie für das, was Sie wollen, aber es wurde viel an Techniken gearbeitet, um immer verfeinerte LPs (SDPs) zu entwerfen, die dem gewünschten Ganzzahlprogramm immer näher kommen. Eine gute Referenz, die diese Ansätze überprüft, ist von Monique Laurent: Ein Vergleich der Sherali-Adams-, Lovasz-Schrijver- und Laserre-Relaxationen für die 0-1-Programmierung .

Abgesehen davon ist mir keine einzige gute Quelle für Referenzen bekannt: Ich nehme an, Sie haben zumindest die relevanten Kapitel in Vijay Vaziranis Buch gelesen ?

Suresh Venkat
quelle
Vielen Dank, Ihre erste Referenz ist das, was ich im Sinn hatte und zu vermeiden versuchte, weil ich mir nach Möglichkeit etwas Einfacheres wünschen würde.
Grigory Yaroslavtsev
Vijays Buch beschreibt kurz den Begriff der Integritätslücke und geht dann auf die Diskussion spezifischer Probleme ein, ohne allgemeine Techniken anzugeben. Ich vermute, dass der Begriff der Integralitätslücke und die relevanten Ergebnisse davon sehr unterschiedlich sein können von den Ergebnissen über Approximationsalgorithmen, da das erste ein größtenteils geometrisches Problem ist.
Grigory Yaroslavtsev