Integritätslücke und Approximationsverhältnis

Wenn wir einen Näherungsalgorithmus für ein Minimierungsproblem betrachten, ergibt die Integritätslücke einer IP-Formulierung für dieses Problem eine Untergrenze eines Näherungsverhältnisses für bestimmte Klassen von Algorithmen (wie beispielsweise Rundungs- oder Primal-Dual-Algorithmus). Tatsächlich gibt es viele Probleme, deren bestes Näherungsverhältnis mit der Integritätslücke übereinstimmt.

Einige Algorithmen haben möglicherweise ein besseres Approximationsverhältnis als die Integritätslücke für ein Problem, aber ich weiß nicht, ob ein solches Beispiel existiert oder nicht. Wenn die Antwort ja ist, können Sie einige Beispiele nennen?

Ich weiß, dass einige Probleme mehrere mathematische Formulierungen zulassen. Betrachten Sie in solchen Fällen die mathematische Formulierung mit der geringsten Integritätslücke, solange sie in Polynomzeit gelöst werden kann (möglicherweise verwenden einige Formulierungen Trennungs-Orakel).

Diese Frage steht im Zusammenhang mit [der Frage: Die Bedeutung der Integritätslücke] .

ds.algorithms approximation-algorithms linear-programming integrality-gap Snowie
quelle

Ich würde vermuten, dass geometrische TSP ein Beispiel für ein solches Problem wäre, aber ich habe keine Referenzen.

Jukka Suomela

Und was ist mit Problemen, die ein PTAS unter Verwendung der Schaltstrategie zulassen? Hat einer von diesen eine IP-Formulierung mit einer willkürlich kleinen Integritätslücke?

Jukka Suomela

@Jukka geometrische TSP ist ein gutes Beispiel. Das Beispiel für eine 4/3-Integritätslücke ist eine Metrik mit dem kürzesten Pfad in einem planaren Graphen, und es sollte möglich sein, eine Instanz eines euklidischen TSP oder

TSP in der Ebene mit einer Lücke von

erstellen

ℓ_{1}

$\ell_1$

1 + ϵ

$1+\epsilon$

Luca Trevisan

Ich hörte es als eine interessante offene Frage erwähnen, ob PTASs für Probleme auf planaren Graphen durch Verwendung einer konstanten Anzahl von Pegeln von Sherali-Adams- oder Lasserre-Relaxationen realisiert werden können. (Wo die Konstante von der Näherungsrate abhängt, die man erreichen möchte.) Es sollte bekannt sein oder zumindest mit aktuellen Techniken nachweisbar sein, dass die Graphprobleme, die PTASs in dichten Graphen aufweisen (z. B. Maximalschnitt), auch eine Familie von Polynomen aufweisen Größenrelaxationen mit beliebig kleinen Integritätslücken.

Luca Trevisan

Verwandte Frage: Gibt es ein Problem, das bewiesen ist, dass eine LP mit Polynomgröße nicht das derzeit bekannteste Näherungsverhältnis liefern kann? Kann man so etwas auch für einige eingeschränkte LP-Typen beweisen?

Danu

Antworten:

Wie bereits erwähnt, gibt es einige Beispiele.

Ein klassisches Beispiel ist die maximale Übereinstimmung, bei der die "natürliche" Relaxation (ohne ungerade festgelegte Einschränkungen) eine Lücke von 2 aufweist, während es natürlich einen effizienten Algorithmus gibt. Dieser ist jedoch nicht vollständig qualifiziert, da es eine LP mit Exponentialgröße gibt, die über Ellipsoid gelöst werden kann.

Ein faszinierendes Beispiel ist der Standort einer kapazitiven Einrichtung. Hier hat die natürliche Entspannung eine grenzenlose Integritätslücke. Lokale suchbasierte Algorithmen liefern jedoch konstante Faktorannäherungen.

Ein weiteres sehr interessantes Dokument (obwohl es sich um ein Maximierungsproblem handelt) ist dieses: http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf . Hier weist die LP eine große Lücke auf, und dennoch kann ein Algorithmus, der diese LP verwendet, eine bessere Leistung erbringen.

Kunal
quelle

Vielen Dank. Diese Antwort enthält, wonach ich gesucht habe, insbesondere das FOCS-Papier von Chakrabarty et al. (dieses Papier interessiert mich so sehr). Deshalb setze ich diese Antwort als akzeptiert. Ich suche jedoch immer noch nach weiteren Beispielen, und daher wäre jeder, der andere Beispiele nennen kann, sehr dankbar.

Snowie

Es gibt verschiedene Beispiele, bei denen eine semidefinite Programmierrelaxation eine Approximation ermöglicht, die bekannten Integritätslücken für lineare Programmierrelaxationen überlegen ist.

Beispielsweise hat die standardmäßige lineare Programmierrelaxation von max cut eine Integralitätslücke von 1/2, und dies gilt auch für viel ausgefeiltere lineare Programmierrelaxationen (vgl. De la Vega-Kenyon und Schoenebeck-Trevisan-Tulsiani), aber die Goemans -Williamson SDP-Algorithmus hat Näherung .878 ...

$\Omega(\log n)$ $O(\sqrt{\log n})$

Karloff und Zwick zeigen vielleicht weniger bekannt, dass man mit SDP Max 3SAT in der Version, in der Klauseln 1, 2 oder 3 Liter haben können, innerhalb von 7/8 approximieren kann, während Goemans und Williamson eine lineare Programmierrelaxation untersucht hatten, die sie hatten verwendet, um eine 3/4 Annäherung zu beweisen (Yannakakis hatte 3/4 Annäherung früher durch andere Methoden gegeben), und die Goemans-Williamson-LP-Relaxation von Max 3SAT hat leicht eine Integralitätslücke von 3/4.

Luca Trevisan
quelle

Es gibt auch ein Ergebnis von Grant zur Lösung linearer Systeme über GF_2. Für Gleichungssysteme mit einer guten Lösung haben Sie eine SDP-Integritätslücke (in einer sehr starken Form) von 2, während Sie die Gaußsche Eliminierung verwenden können, um das Problem genau zu lösen.

YI WU
quelle