2.2 KiB
algoritmo di approssimazione di minimal vertex cover problem che fa uso di relax-and-round.
Funzionamento
[!Summary] Si converte il problema da campo degli interi a continuo, lo si risolve con un algoritmo di programmazione lineare, e poi si arrotonda la soluzione in direzione opposta a quella dell'ottimizzazione che si sta effettuando.
Definizione
Si chiede di assegnare una variabile booleana Optimal_{Node} a ciascun nodo di un grafo:
0se il nodo di un grafo non è parte della soluzione ottima1se lo è
Si stabilisce un vincolo per descrivere un vertex cover:
\def \varNodeA {{\color{LightCoral} Node_A}}
\def \varNodeB {{\color{Coral} Node_B}}
\forall\ (\varNodeA, \varNodeB) \in Edges :
\begin{cases}
\
Optimal_{\varNodeA} + Optimal_{\varNodeB} \geq 1
\\
\end{cases}
[!Tip]- Significato del vincolo "Per ogni arco di un grafo, scegli almeno uno dei due nodo di un grafo ai suoi estremi.
Infine, si definisce la funzione obiettivo come:
\min \sum_{Node}^{Nodes} Optimal_{Node}
relax-and-round
Invece di richiedere di assegnare variabili numero booleano, richiediamo al risolutore di programmazione lineare di assegnare variabili numero reale:
0 \leq Relaxed_{Node} \leq 1
relax-and-round
Si selezionano tutti i nodo di un grafo tali che:
\frac{1}{2} \leq Relaxed_{Node}
algoritmo corretto
[!Success] Si forma un vertex cover valido.
fattore di approssimazione
Possiamo notare che, da come abbiamo effettuato l'arrotondamento:
Relaxed_{Node} \leq \frac{1}{2} \cdot Optimal_{Node}
Portando dall'altra parte:
2 \cdot Relaxed_{Node} \leq Optimal_{Node}
Allora, questa disuguaglianza sarà applicabile anche alla funzione costo:
2 \cdot \sum_{Node}^{Nodes} Relaxed_{Node} \leq \sum_{Node}^{Nodes} Optimal_{Node}
Questo significa che il funzione costo della versione rilassata è al massimo il doppio di quella soluzione ottima, e che quindi il fattore di approssimazione è:
\Large 2