Approximationsalgorithmen, die in exakten Algorithmen verwendet werden

Approximationsalgorithmen können eine Ausgabe bis zu einem konstanten Faktor liefern. Dies ist etwas weniger zufriedenstellend als exakte Algorithmen.

Konstante Faktoren werden jedoch in der zeitlichen Komplexität ignoriert.

Ich frage mich also, ob der folgende Trick möglich ist oder angewendet wurde, um ein Problem zu lösen. :$B \circ A$

1. Verwenden Sie einen Approximationsalgorithmus zur Lösung von Problem , um die Lösung S innerhalb eines konstanten Faktors zu erhalten.$A$$S$
2. Verwenden Sie einen exakten Algorithmus, um Problem lösen , dessen Laufzeit vom Gewicht von S abhängt, aber funktioniert, solange S eine korrekte Lösung ist.$B$$S$$S$

Auf diese Weise ist die Approximation eine "Unterprozedur" eines exakten Algorithmus, und der in Schritt 1 verlorene konstante Faktor wird in Schritt 2 verschluckt.

Ein Beispiel aus der parametrisierten Komplexität ist eine Kernelisierung für das Vertex-Cover-Problem unter Verwendung eines Theorems von Nemhauser und Trotter.

In dem Problem der minimalen Scheitelpunktabdeckung erhalten wir einen ungerichteten Graphen G, und wir müssen eine Scheitelpunktabdeckung von G mit minimaler Größe finden. Eine Scheitelpunktabdeckung eines ungerichteten Graphen ist eine Scheitelpunktuntermenge, die alle Kanten berührt.

Hier ist ein genauer Algorithmus, der in der ersten Phase eine Näherung verwendet.

Phase 1: Richten Sie die ganzzahlige lineare Programmierformulierung für das Problem der minimalen Scheitelpunktabdeckung ein . Es ist bekannt (oder leicht zu zeigen), dass eine grundlegende optimale Lösung der linearen Programmierrelaxation halbintegral ist (dh jede Koordinate ist entweder 0, 1 oder 1/2). Eine solche grundlegende optimale Lösung kann durch einen üblichen Polynomzeitalgorithmus für die lineare Programmierung gefunden werden (oder in diesem speziellen Fall können wir sie als Netzwerkflussproblem formulieren, um sie kombinatorisch in Polynomzeit zu lösen). Mit einer solchen grundlegenden optimalen Lösung runden wir sie auf, um eine praktikable Lösung für das ursprüngliche Problem der ganzzahligen linearen Programmierung zu erhalten. Sei S die entsprechende Scheitelpunktuntermenge. Es ist gut zu beachten, dass S eine 2-Näherung der gegebenen minimalen Scheitelpunktabdeckungsinstanz ist.

Phase 2: Finden Sie eine minimale Scheitelpunktabdeckung in dem durch S induzierten Teilgraphen (zum Beispiel durch eine erschöpfende Suche). Ein Satz von Nemhauser und Trotter besagt, dass dieser Untergraph eine optimale Lösung des ursprünglichen Eingabegraphen enthält. Die Richtigkeit dieses Ansatzes folgt also.

Sie können ein Buch von Niedermeier über Algorithmen mit festen Parametern für diesen Algorithmus konsultieren .

Ein Beispiel ist im Zusammenhang mit Baumzerlegungen und Grafiken von kleinen Baumweite.

$B$

$B$$A$

$A$$A$$A$$A$$B$

$B$$A$

$B$$A$$A$$B$

Ein Beispiel für einen Approximationsalgorithmus, der zur exakten Lösung konvergiert, wäre der Ellipsoid-Algorithmus zum Lösen von LPs. Wenn die Koeffizienten rational sind, kann man einen Mindestabstand zwischen zwei Eckpunkten des realisierbaren Polytops berechnen. Der Ellipsoid-Algorithmus berechnet nun wiederholt ein immer kleineres Elliposoid, das die optimale Lösung enthalten muss. Sobald das Elliposoid klein genug ist, um nur einen solchen einzelnen Scheitelpunkt zu enthalten, haben Sie im Wesentlichen den optimalen Scheitelpunkt gefunden. Deshalb ist LP schwach polynomisch.

$k$

Wenn Sie ein Feld weiter gehen - viele Algorithmen, die der Änderungstechnik folgen (nehmen Sie eine Zufallsstichprobe - und dann einige Korrekturen vornehmen, um das zu erhalten, was Sie wollen), fallen Sie in ein solches Framework. Ein niedliches Beispiel ist der Algorithmus zur Berechnung des Medians mithilfe von Zufallsstichproben (siehe das Buch von Motwani und Raghavan). Es gibt viele solcher Beispiele - wohl viele der randomisierten inkrementellen Algorithmen in Computational Geometry fallen in diesen Rahmen.

Viele ausgangssensitive Algorithmen verwenden diese Technik. Hier ist zum Beispiel ein einfaches Problem, bei dem diese Technik angewendet werden kann:

Problem . Sie erhalten ein Array A [1 .. n ], in dem jedes Element höchstens k Positionen von der Position entfernt ist, an der es gewesen wäre, wenn A sortiert worden wäre.

Zum Beispiel könnte A [1..7], das unten gezeigt wird, ein Eingabearray für k = 2 sein.

Problemquelle: Algo Muse Archive.