Errore limite inferiore per un algoritmo per la copertura dei vertici

Question

Ho il seguente algoritmo randomizzato per il problema della copertura dei vertici.Permettere $B_0$ essere l'output impostato:

• Mettiamo un po' d'ordine $e_1, e_2, ..., e_m$ su tutti i bordi del gruppo di bordi E di G, e impostare $B_0 = \insiemevuoto$.
• aggiungere a $B_0$ tutti i vertici isolati, cioèquelli senza bordi incidenti.
• Per ogni bordo $e$ In $e_1, e_2, ..., e_m$
  • se entrambi gli endpoint di $e$ non contenuto in $B_0$, Poi
  • lancia una moneta equilibrata decidendo quale dei punti finali scegliere e aggiungi questo punto finale $B_0$.

Come posso dimostrarlo, per ogni costante $c \geq 1$, l'algoritmo potrebbe produrre a $B_0$ con $ | B_0 | ge c | opt | $?

Answer 1

Correggi un grafico stellare di $c + 1$ vertici.Un grafico stellare è un vertice connesso a tutti gli altri vertici nel grafico (un vertice universale chiamato centro) e tutti gli altri vertici sono a coppie non adiacente.Ecco un esempio visivo. $c$ è il centro della stella.

Ora una soluzione ottimale è impacchettare il centro della stella.La dimensione di questa soluzione è uguale a 1.Per ciascun bordo, supponiamo che il nostro algoritmo impacchi l'altra estremità del bordo (il vertice non universale), quindi dobbiamo impacchettare tutti i vertici del grafico tranne il centro e quindi dobbiamo impacchettare $c$ vertici diversi.In totale otteniamo $ | B_0 | = C | opt | $ per qualsiasi valore arbitrario ma fisso di $c$.

---

NotaUna semplice modifica dell'algoritmo produce un algoritmo di approssimazione derandomizzato con una dimensione della risposta al massimo doppia rispetto a quella ottimale.Funziona come segue:se entrambi i punti finali del bordo non sono presenti $B_0$, Poi aggiungi Entrambi endpoint a $B_0$ e ripetere.

Il motivo per cui funziona è semplice.I bordi, a cui vengono aggiunti i loro punti finali per una corrispondenza massima e quindi aggiungiamo il doppio del numero di vertici in una corrispondenza massima alla copertura.Si noti che la dimensione di una corrispondenza in un grafico è un limite inferiore alla dimensione di una copertura minima di vertici e quindi aggiungiamo al massimo il doppio dei vertici rispetto alla dimensione della copertura minima di vertici.