Algoritmo minimo della copertura del vertice con programmazione lineare

Question

Considera il seguente algoritmo: dato un grafico $ G $ con $ n $ Vertici, impostare Un problema di programmazione lineare lp dove c'è una variabile $ x_i $ per ogni vertice $ v_i $ di $ G $ , ogni variabile può prendere valore $ \ geq 0 $ , per ciascuno Edge $ v_av_b $ di $ G $ Imposta il vincolo $ x_a + x_b \ geq 1 $ . La funzione obiettivo è $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ . Trova la variabile (o una delle variabili) $ x_i $ , tra le variabili non impostati su $ 0 $ , che impostato su $ 0 $ dà il valore minimo della funzione obiettivo. Aggiungere il vincolo $ x_i= 0 $ a lp . Ripeti fino a quando la soluzione ottimale di lp è integer (che ciascuna variabile prende valore in $ \ sinistra \ {0; 1 \ destra \} $ ).

Sto cercando un grafico in cui i vertici associati alle variabili che prendono valore $ 1 $ nella soluzione finale ottimale di lp sono Non una copertura di vertice minima di $ G $ (se esiste).

Answer 1

Considera il grafico

  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

.

Impostazione $ x_1, x_2, x_3, x_6 $ o $ x_7 $ su 0 dà il tuo LPUn valore di 4, mentre impostando $ x_4 $ o $ x_5 $ su 0 dà il tuo Valore del tuo LP un valore di5. Tuttavia, se si imposta $ x_1= 0 $ , verrà finalmente ottenuto una copertura vertice della taglia 5, mentre il coperchio ottimale del vertice è di dimensioni 4.

.