Die Bedeutung der Integritätslücke

Ich hatte immer Probleme, die Wichtigkeit der Integritätslücke (IG) und ihrer Grenzen zu verstehen . IG ist das Verhältnis von (der Qualität von) einer optimalen ganzzahligen Antwort zu (der Qualität von) einer optimalen realen Lösung der Entspannung des Problems. Betrachten wir als Beispiel Vertex Cover (VC). Man kann sagen, dass VC eine optimale ganzzahlige Lösung der folgenden linearen Gleichungen findet:

Wir haben Null / Eins bewertet Variablen für jeden Scheitelpunkt S des Graphen . Die Gleichungen lauten: für und für jede Kante . Wir suchen nach Werten, die . v ∈ V ( G ) G 0 ≤ x v ≤ 1 v ∈ V ( G ) 1 ≤ x v + x u u v ∈ E ( G ) Σ v ∈ V ( G ) x $x_v$$v \in V(G)$$G$$0 \leq x_v \leq 1$$v\in V(G)$$1 \leq x_v+x_u$$uv \in E(G)$$\sum_{v \in V(G)} x_v$

Die Entspannung dieses Problems ermöglicht reelle Werte zwischen und sodass der Lösungsraum größer ist und eine optimale reelle Lösung kleiner sein kann als eine optimale ganzzahlige Lösung, die wir finden möchten. Daher müssen wir einen "Rundungs" -Prozess für die optimale reelle Antwort durchführen, die aus der linearen Programmierung erhalten wird, um eine ganzzahlige Lösung zu finden. Die optimale ganzzahlige Lösung liegt zwischen der optimalen reellen Lösung und dem Ergebnis des Rundungsprozesses. IG ist das Verhältnis einer optimalen ganzzahligen Lösung zu einer optimalen reellen Lösung und sagt nichts über den Rundungsprozess aus. Der Rundungsprozess kann (theoretisch) die reale Lösung vollständig ignorieren und die optimale ganzzahlige Lösung direkt berechnen.$0$$1$

Warum sind die Leute daran interessiert, die Grenzen der IG zu beweisen?

Integritätslücken repräsentieren im Wesentlichen die inhärenten Grenzen einer bestimmten linearen oder konvexen Relaxation bei der Approximation eines ganzzahligen Programms. Wenn die Integritätslücke einer bestimmten Relaxation , kann im Allgemeinen kein auf dieser Relaxation basierender Approximationsalgorithmus eine bessere Leistung als eine x- Approximation erhoffen . Zumindest sind Integritätslücken für Algorithmenentwickler von Interesse, da sie Einschränkungen bei bestimmten Techniken nahelegen. $x$$x$

Warum also nicht einfach eine andere LP-Entspannung einfallen lassen oder zu anderen Techniken wechseln und weitermachen? Lineare und konvexe Programmierung haben sich als zentral für Approximationsalgorithmen erwiesen. Für viele Probleme ist die Integritätslücke einer natürlichen LP- oder SDP-Formulierung gleich dem Approximationsverhältnis des besten Algorithmus sowie der Härte des Approximationsverhältnisses. Dies ist nur eine empirische Beobachtung, aber es bedeutet, dass der Nachweis einer Integritätslücke viel stärkere Konsequenzen eines verbesserten Algorithmus oder einer niedrigeren Schranke haben kann.

Es kann tiefere und strengere Gründe für dieses Phänomen geben. Beispielsweise ist unter der Annahme der einzigartigen Spielevermutung bekannt, dass das Approximationsverhältnis und das Inapproximabilitätsverhältnis für Bedingungserfüllungsprobleme gleich der Integritätslücke einer einfachen SDP-Relaxation ist (siehe Optimale Algorithmen und Inapproximabilitätsergebnisse für jeden CSP? Von Prasad Raghavendra).

Schließlich repräsentieren Integritätslücken bedingungslose Untergrenzen. Normalerweise müssen wir uns auf unbewiesene Annahmen stützen (z. B. ), wenn wir in unteren Grenzen Fortschritte erzielen möchten, aber bei eingeschränkten Berechnungsmodellen können wir manchmal ohne diese auskommen (siehe Vorlesungsunterlagen von Luca Trevisan). Integritätslücken, die eher rein geometrisch als rechnerisch sind, sind ein Weg, um ziemlich mächtige Untergrenzen zu erreichen, ohne das Gepäck zusätzlicher Annahmen.$P \neq NP$

Angenommen, Ihr interessierendes Problem ist ein Minimierungsproblem und Sie haben ungefähren Algorithmus entwickelt. Wenn Ihr Algorithmus für eine bestimmte Eingabe eine Lösung mit den Kosten c ausgibt, ergibt die Berechnung des Algorithmus plus seiner Analyse ein Zertifikat, das für diese Eingabe das Optimum von mindestens a / c ergibt . Offensichtlich a ist zumindest die optimale, so dass für jeden Eingang wir in der Lage sind , auf den optimalen einem niedrigeren zu zertifizieren gebunden , die zumindest ein 1 / c Bruchteil des optimalen selbst.$a$$c$$a/c$$a$$1/c$

Bei allen mir bekannten Algorithmen, die auf konvexen (LP und SDP) Relaxationen basieren, ist die zertifizierte Untergrenze für das Optimum durch das Optimum der Relaxation gegeben. Wenn die Relaxation die Integralitätslücke , ist es nicht möglich, ein besseres Approximationsverhältnis als I zu erzielen , es sei denn, man führt in der Analyse eine Technik für die untere Grenze für das Optimum ein, die stärker ist als die durch die Relaxation bereitgestellte untere Grenze.$I$$I$

Die Integritätslücke ist ein nützlicher Indikator dafür, wie gut eine IP angenähert werden kann. Es ist vielleicht besser, informell und intuitiv darüber nachzudenken. Eine hohe Integritätslücke impliziert, dass bestimmte Methoden nicht funktionieren. Bestimmte primäre / duale Methoden hängen beispielsweise von einer kleinen Integritätslücke ab. Für die Standard-Ur-Vertex-Cover-LP fordert die Doppel-LP eine maximale Übereinstimmung an. In diesem Fall können wir Folgendes tun:

• finde eine optimale fraktionale Lösung für die doppelte LP (maximale fraktionale Übereinstimmung)$\boldsymbol{y}$
• multipliziere die Lösung mit dem Faktor 2 (verdopple alle Kantengewichte)$\boldsymbol{y}$
• wandeln dies eine machbare integral für das Erst - LP (jede Kante Hälfte seines Gewichtes vom gibt Vektor zu jedem seiner Endpunkte in der Vektor, dann wird jeder ist ersetzt durch ).2 y x x i min ( ⌊ x i ⌋ , 1 $\boldsymbol{x}$$2\boldsymbol{y}$$\boldsymbol{x}$$x_i$$\min(\lfloor x_i\rfloor, 1)$

In diesem Fall funktioniert diese einfache Strategie und wir erhalten eine praktikable integrale Lösung für die ursprüngliche LP, deren Gewicht nicht mehr als das Zweifache des Gewichts einer praktikablen Lösung für die doppelte LP beträgt. Da das Gewicht einer möglichen Lösung für die duale LP für OPT eine Untergrenze ist, handelt es sich um einen 2-Approximationsalgorithmus.

Woher kommt nun die Integritätslücke? Der IG ist in diesem Fall 2, aber das allein bedeutet nicht, dass der Algorithmus funktioniert. Es deutet eher darauf hin, dass es funktionieren könnte. Und wenn die IG mehr als 2 wäre, würde dies garantieren, dass die einfache Strategie nicht immer funktioniert. Zumindest müssten wir die duale Lösung durch die IG multiplizieren. Die Integritätslücke sagt uns manchmal, was nicht funktioniert. Die Integritätslücke kann auch angeben, auf welche Art von Näherungsfaktor wir hoffen können. Eine kleine Integritätslücke lässt vermuten, dass die Untersuchung von Rundungsstrategien usw. ein lohnender Ansatz sein könnte.

Ein interessanteres Beispiel ist das Problem der Schlagmenge und die leistungsstarke Methode zur Approximation des Problems mit -netzen (Brönnimann & Goodrich, 1995) . Viele Probleme können als Instanzen von Hitting Set formuliert werden, und eine Strategie, die für viele Probleme erfolgreich war, besteht darin, dies zu tun, dann einfach einen guten Netzfinder zu finden, dh einen Algorithmus, um kleine Netze zu konstruieren und alles durchzudrehen der B & G Meta-Algorithmus. Daher versuchen Leute (ich eingeschlossen), Netzsucher für eingeschränkte Instanzen von Hitting Set zu finden, die für jedes ein -Netz der Größe erstellen können , in dem die Funktionε ε ε f ( 1 / ε ) f f ( 1 / ε ) = O ( 1 / ε ) O ( 1 $\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$f(1/\varepsilon)$$f$sollte so klein wie möglich sein. Mit ist ein typisches Ziel; dies würde eine -Näherung ergeben.$f(1/\varepsilon) = \mathcal{O}(1/\varepsilon)$$\mathcal{O}(1)$

Wie sich herausstellt, ist die bestmögliche Funktion durch die Integritätslücke einer bestimmten LP für Hitting Set begrenzt (Even, Rawitz, Shahar, 2005) . Insbesondere erfüllen die optimalen Integral- und . Für uneingeschränkte Fälle von Hitting Set ist die Integritätslücke , aber wenn ein anderes Problem als Hitting Set formuliert wird, kann die IG niedriger sein. In diesem Beispiel zeigen die Autoren, wie man -netze der Größe$f$$\mathrm{OPT}_I \leq f(\mathrm{OPT}_f)$$\Theta(\log(m))$$\varepsilon$$\mathcal{O}((1/\varepsilon) \log \log (1/\varepsilon))$für die eingeschränkten Instanzen von Hitting Set, die dem Problem des Treffens von achsparallelen Boxen entsprechen. Auf diese Weise verbessern sie den bekanntesten Näherungsfaktor für dieses Problem. Es ist ein offenes Problem, ob dies verbessert werden kann oder nicht. Wenn für diese eingeschränkten Hitting Set-Instanzen die IG für die Hitting Set-LP , ist es unmöglich, einen Netzfinder zu entwerfen, der -netze der Größe garantiert. , da dies die Existenz eines Algorithmus implizieren würde, der integrale der Größe garantiert , aber seit$\Theta(\log \log m)$$\varepsilon$$o((1/\varepsilon) \log \log (1/\varepsilon))$ O P T f ≤$o(\mathrm{OPT}_f \log\log \mathrm{OPT}_f)$$\mathrm{OPT}_f\leq m$Dies würde eine geringere Integritätslücke bedeuten. Wenn also die Integritätslücke groß ist, könnte der Nachweis dafür verhindern, dass die Leute ihre Zeit damit verschwenden, nach guten Netzsuchern zu suchen.

Wenn Sie einen Näherungsalgorithmus für ein NP-hartes Maximierungsproblem entwickeln, gibt es mehrere Werte, die Sie interessieren könnten: Es gibt OPT, den optimalen Wert Ihres Problems, der der gleiche ist wie OPT (IP), das Optimum Wert einer korrekten IP-Formulierung Ihres Problems. Es gibt auch OPT (LP), den optimalen Wert für die lineare Entspannung Ihrer IP.

$OPT(LP) \geq OPT(IP)$

Schließlich gibt es V, den Wert der Lösung, die Sie erhalten, indem Sie die LP-Lösung runden. Sie möchten in der Lage sein, zu beweisen, zu zeigen, dass Ihr Algorithmus eine Näherung ist, aber es ist häufig nicht möglich, dies direkt zu tun, da Sie kein haben Halten Sie den Lösungsraum fest. Stattdessen wird fast immer bewiesen, dass . Dies impliziert natürlich , ist aber stärker. Insbesondere wenn die Integritätslücke Ihrer IP-Formulierung größer als , ist die obige Aussage im Allgemeinen falsch, da Ihre Rundungsprozedur zu einer integralen Lösung führt. cV≥OPT(LP$V > \frac{OPT(IP)}{c}$$c$ V>OPT(IP$V \geq \frac{OPT(LP)}{c}$$V > \frac{OPT(IP)}{c}$$c$

Der springende Punkt ist also: Die LP gibt Ihnen eine Lösung, von der Sie wissen, dass sie "gut" ist, und Sie möchten sie auf etwas abrunden, das "fast so gut" ist. Wenn die Integritätslücke groß ist, ist dies im Allgemeinen unmöglich, da es niemals ein Verfahren geben wird, das garantiert eine integrale Lösung liefert, die "am besten" ist wie eine LP-Lösung - denn manchmal gibt es diese nicht!

Sie haben Recht, dass die Integritätslücke einer Relaxation als solche nichts mit einem Rundungsalgorithmus zu tun hat. Das sind zwei verschiedene Begriffe. Eine Integritätslücke ist eine Eigenschaft einer bestimmten Entspannung. Das heißt, wie viel größer ist der Wert dieser Entspannung im Vergleich zum optimalen Integralwert?

Warum interessieren uns lineare / konvexe Relaxationen? Effiziente Approximation eines Integralwerts. Daher sprechen wir in der Regel nur dann von Relaxationen, wenn der optimale Wert schwer zu berechnen ist und wir an effizienten Approximationen interessiert sind. Integritätslücken zeigen uns die inhärenten Grenzen dessen, was mit solchen Techniken erreicht werden kann.

Also, warum wir kümmern uns um Algorithmen auf der Oberseite der Entspannung Runden? Wir verwenden Rundungsalgorithmen, um das algorithmische Problem zu lösen, eine nahezu optimale Lösung zu finden, anstatt nur den Wert einer optimalen Lösung zu approximieren . Darüber hinaus werden häufig Rundungsalgorithmen verwendet, um die Integritätslücke einer Relaxation an erster Stelle zu begrenzen.

Technisch gesehen ist die Integritätslücke für eine bestimmte IP-Formulierung, nicht (wie Sie es formuliert haben) das Verhältnis zwischen der besten linearen Relaxation und der optimalen Lösung (die über ALLE IP-Formulierungen zu quantifizieren scheint).

Eine Integritätslücke ist wichtig, da sie die Grenzen der jeweiligen verwendeten LP-Formulierung aufzeigt. Wenn ich weiß, dass eine bestimmte Relaxation eine Integralitätslücke von , dann weiß ich auch, dass ich eine andere Formulierung verwenden muss , wenn ich jemals hoffe, eine Grenze von besser als zu beweisen .$c$$c$

Es gab eine sehr interessante Arbeit "Über den Vorteil der Netzwerkkodierung zur Verbesserung des Netzwerkdurchsatzes", die zeigte, dass die Integritätslücke der "bidirektionalen Schnittrelaxation" für das Steiner-Baum-Problem genau einer Art "Kodierungsvorteil" in der Netzwerkkommunikation entspricht. Ich kenne nicht viele ähnliche Papiere. Man sollte jedoch auch beachten, dass scheinbar bessere LP-Relaxationen für das Steiner-Baum-Problem bekannt sind (siehe z. B. den neuen hypergraphischen LP-basierten Approximationsalgorithmus von Byrka et al. In STOC 2010) LP).

Die meisten Antworten haben bereits den Hauptgrund für die Sorge um die Integritätslücke angesprochen, nämlich, dass ein Näherungsalgorithmus, der ausschließlich auf der Verwendung der durch die Relaxation bereitgestellten Schranke basiert, nicht darauf hoffen kann, ein besseres Verhältnis als die Integritätslücke zu beweisen. Lassen Sie mich zwei weitere Meta-Gründe nennen, warum die Integritätslücke ein nützlicher Leitfaden ist. Für eine große Klasse von kombinatorischen Optimierungsproblemen zeigt die Äquivalenz von Trennung und Optimierung, dass genaue Algorithmen eng mit der konvexen Hülle der möglichen Problemlösungen zusammenhängen. Somit sind die geometrische und algorithmische Perspektive sehr eng miteinander verbunden. Eine ähnliche formale Äquivalenz ist für Approximationsalgorithmen nicht bekannt, sie ist jedoch ein nützlicher Leitfaden - Algorithmen gehen Hand in Hand mit geometrischen Relaxationen. Algorithmische Innovationen entstehen, wenn Menschen ein konkretes Ziel haben, sich zu verbessern.