Fehleruntergrenze für einen Algorithmus zur Scheitelpunktabdeckung

Question

Ich habe den folgenden randomisierten Algorithmus für das Scheitelpunktabdeckungsproblem.Lassen $B_0$ sei die Ausgabemenge:

• Bringen Sie eine Ordnung in Ordnung $e_1, e_2, ..., e_m$ über alle Kanten in der Kantenmenge E von G und set $B_0 = \emptyset$.
• Hinzufügen zu $B_0$ alle isolierten Eckpunkte, d.h.diejenigen ohne einfallende Kanten.
• Für jede Kante $e$ In $e_1, e_2, ..., e_m$
  • wenn beide Endpunkte von $e$ nicht enthalten $B_0$, Dann
  • Werfen Sie eine faire Münze, entscheiden Sie, welchen der Endpunkte Sie auswählen möchten, und fügen Sie diesen Endpunkt hinzu $B_0$.

Wie kann ich das für jede Konstante beweisen? $c \geq 1$, könnte der Algorithmus a erzeugen $B_0$ mit $ | B_0 | ge c | opt | $?

Answer 1

Korrigieren Sie ein Sterndiagramm von $c + 1$ Eckpunkte.Ein Sterndiagramm ist ein Scheitelpunkt, der mit allen anderen Scheitelpunkten im Diagramm verbunden ist (ein universeller Scheitelpunkt, der als Zentrum bezeichnet wird), und alle anderen Scheitelpunkte sind paarweise nicht benachbart.Hier ist ein visuelles Beispiel. $c$ ist das Zentrum des Sterns.

Eine optimale Lösung besteht nun darin, die Mitte des Sterns zu packen.Die Größe dieser Lösung beträgt 1.Angenommen, unser Algorithmus packt für jede Kante das andere Ende der Kante (den nichtuniversellen Scheitelpunkt), dann müssen wir alle Scheitelpunkte des Diagramms außer der Mitte packen und daher müssen wir packen $c$ verschiedene Eckpunkte.Insgesamt bekommen wir $ | B_0 | = C | opt | $ für jeden beliebigen, aber festen Wert von $c$.

---

NotizEine einfache Modifikation des Algorithmus ergibt einen derandomisierten Approximationsalgorithmus mit einer Antwortgröße, die höchstens doppelt so groß ist wie das Optimum.Es geht wie folgt:wenn beide Endpunkte der Kante nicht vorhanden sind $B_0$, dann füge hinzu beide Endpunkte zu $B_0$ und iterieren.

Der Grund, warum das funktioniert, ist einfach.Die Kanten, deren Endpunkte für ein maximales Matching hinzugefügt werden, und daher fügen wir bei einem maximalen Matching die doppelte Anzahl an Eckpunkten zur Abdeckung hinzu.Beachten Sie, dass die Größe eines Matchings in einem Diagramm eine Untergrenze für die Größe einer minimalen Scheitelpunktabdeckung darstellt und wir daher höchstens doppelt so viele Scheitelpunkte hinzufügen wie die Größe der minimalen Scheitelpunktabdeckung.