Randomizzato Arrotondamento di soluzioni per programmi lineari

Question

Integer Linear Programming (ILP) è uno strumento incredibilmente potente per l'ottimizzazione combinatoria. Se siamo in grado di formulare qualche problema come un'istanza di un ILP poi risolutori sono garantiti per trovare l'ottimo globale. Tuttavia, applicando soluzioni integrali trovi runtime è esponenziale nel caso peggiore. Per far fronte a questa barriera, possono essere utilizzati vari metodi di approssimazione sono collegati ILPS,

• Primal-Dual Schema
• randomizzato arrotondamento

Lo schema Primal-Dual è un metodo versatile che ci offre un modo "impaccato" a venire con un algoritmo greedy e dimostrare i suoi limiti di approssimazione che utilizza una doppia LP rilassato. Risultanti algoritmi combinatori tendono ad essere molto veloce ed eseguire abbastanza bene nella pratica. Tuttavia la sua relazione con la programmazione lineare è vicina legata all'analisi. Inoltre a causa di questa analisi, si può facilmente dimostrare che i vincoli non siano violati.

arrotondamento randomizzato adotta un approccio differente e risolve il LP rilassata (con punto interno o metodi ellissoidali) e variabili giri secondo alcuni distribuzione di probabilità. Se i limiti di approssimazione può essere provato questo metodo, come lo schema Primal-Dual, è molto utile. Tuttavia, una parte non è del tutto chiaro per me:

schemi di arrotondamento Come non randomizzati dimostrano che i vincoli non siano violati?

Sembrerebbe che ingenuamente lanciando una moneta, mentre con un conseguente soluzione di 0-1, potrebbe violare i vincoli! Qualsiasi aiuto illuminante questa edizione sarebbe apprezzato. Grazie.

Answer 1

Naturalmente, se rotondo, si deve verificare che arrotondamento conserve di fattibilità.

Facciamo ad esempio considerare la rilassato VERTEX-COVER LP formulazione. $$ \ Begin {array} {} lll \ Text {min} e \ sum_ {v \ in V} c (v) x_v & \\ \ Text {s.t.} & X_u + x_v \ GE1, e \ quad (u, v) \ in E \\ & X_v \ ge 0. & \ quad v \ in V \ End {array} $$

E 'noto che la soluzione a questo problema è la metà-integrale, cioè, ogni variabile è o $ 0 $, $ 1 $, o $ 1/2 $. Lo schema di arrotondamento funziona come segue, ogni volta che la soluzione contiene $ x_v = 1/2 $ si fino rotondo e impostare $ x_v = 1 $. I vincoli della ILP erano $$ \ Begin {array} {} lll & X_u + x_v \ GE1, e \ quad (u, v) \ in E \\ & X_v \ in \ {0,1 \}. & \ Quad v \ in V \ End {array} $$ Entrambi i vincoli sono soddisfatti dopo l'arrotondamento. E si ha un bel 2-approssimazione.

Answer 2

:

Sì, questo è fonte di confusione nella prima vista.

Lo vedo in questo modo:

step1) generano una soluzione programma lineare [tutti i vincoli dei programmi lineari sono soddisfatte qui - tranne che non è la soluzione Intero],

step2) a caso esso (cambiare il valore in numeri interi in base a una distribuzione di probabilità si seleziona),

Fase 3) assicurarsi che la soluzione randomizzato è corretta (facendo poche modifiche su di esso).

Ad esempio, nel set-cover. Dopo la randomizzazione, si può finire con una collezione di insiemi che non sono necessariamente una copertura set. In questo caso, è necessario aggiungere alcuni set che coprono tutti gli elementi scoperti (e, quindi, si ottiene la soluzione che si desidera).

Per evitare tali grandi cambiamenti nel randomizzati soluzione di programma lineare, seguire uno studio randomizzato di arrotondamento schema che garantisce, un'alta probabilità che si trovi una soluzione dopo l'arrotondamento (vale a dire che non sarà necessario fare molti cambiamenti nella soluzione programma lineare, al fine di prendi ciò che vuoi).

Vedere questo per un riferimento: 1