Arrotondamento randomizzato - Randomized rounding

All'interno dell'informatica e della ricerca operativa , molti problemi di ottimizzazione combinatoria sono computazionalmente intrattabili da risolvere esattamente (fino all'ottimalità). Molti di questi problemi ammettono algoritmi di approssimazione veloce ( tempo polinomiale ) , ovvero algoritmi che sono garantiti per restituire una soluzione approssimativamente ottimale dato qualsiasi input.

L'arrotondamento randomizzato ( Raghavan & Tompson 1987 ) è un approccio ampiamente utilizzato per la progettazione e l'analisi di tali algoritmi di approssimazione . L'idea di base è usare il metodo probabilistico per convertire una soluzione ottima di un rilassamento del problema in una soluzione approssimativamente ottima del problema originale.

Panoramica

L'approccio di base prevede tre passaggi:

1. Formulare il problema da risolvere come programma lineare intero (ILP).
2. Calcolare una soluzione frazionaria ottimale per il rilassamento della programmazione lineare (LP) dell'ILP.${\displaystyle x}$
3. Arrotondare la soluzione frazionaria di LP a una soluzione intera di ILP.${\displaystyle x}$${\displaystyle x'}$

(Sebbene l'approccio sia più comunemente applicato con programmi lineari, a volte vengono utilizzati altri tipi di rilassamenti. Ad esempio, vedere l' algoritmo di approssimazione Max-Cut basato sulla programmazione semidefinita di Goemans e Williamson .)

La sfida nella prima fase consiste nello scegliere un programma lineare intero adatto. È richiesta la familiarità con la programmazione lineare, in particolare la familiarità con la modellazione di problemi utilizzando programmi lineari e programmi lineari interi. Ma, per molti problemi, esiste un programma lineare intero naturale che funziona bene, come nell'esempio Set Cover di seguito. (Il programma lineare intero dovrebbe avere un piccolo gap di integralità ; infatti l'arrotondamento randomizzato è spesso usato per dimostrare i limiti sui gap di integralità.)

Nella seconda fase, la soluzione frazionaria ottimale può essere tipicamente calcolata in tempo polinomiale utilizzando qualsiasi algoritmo di programmazione lineare standard .

Nella terza fase, la soluzione frazionaria deve essere convertita in una soluzione intera (e quindi una soluzione del problema originale). Questo è chiamato arrotondamento della soluzione frazionaria. La soluzione intera risultante dovrebbe (provabilmente) avere un costo non molto maggiore del costo della soluzione frazionaria. Ciò assicurerà che il costo della soluzione intera non sia molto maggiore del costo della soluzione intera ottimale.

La tecnica principale utilizzata per eseguire il terzo passaggio (arrotondamento) consiste nell'utilizzare la randomizzazione, quindi utilizzare argomenti probabilistici per vincolare l'aumento di costo dovuto all'arrotondamento (seguendo il metodo probabilistico della combinatoria). Lì, vengono utilizzati argomenti probabilistici per mostrare l'esistenza di strutture discrete con proprietà desiderate. In questo contesto, si usano tali argomenti per mostrare quanto segue:

Data una qualsiasi soluzione frazionaria del PL, con probabilità positiva il processo di arrotondamento randomizzato produce una soluzione intera che si approssima${\displaystyle x}$${\displaystyle x'}$${\displaystyle x}$ secondo qualche criterio voluto.

Infine, per rendere computazionalmente efficiente il terzo passaggio, si mostra che si approssima con alta probabilità (in modo che il passaggio possa rimanere randomizzato) o si dedomizza il passaggio di arrotondamento, tipicamente utilizzando il metodo delle probabilità condizionate . Quest'ultimo metodo converte il processo di arrotondamento randomizzato in un efficiente processo deterministico che garantisce il raggiungimento di un buon risultato. ${\displaystyle x'}$${\displaystyle x}$

Confronto con altre applicazioni del metodo probabilistico

La fase di arrotondamento randomizzato differisce dalla maggior parte delle applicazioni del metodo probabilistico per due aspetti:

1. La complessità computazionale della fase di arrotondamento è importante. Dovrebbe essere implementabile da un veloce (per esempio un tempo polinomiale ) algoritmo .
2. La distribuzione di probabilità alla base dell'esperimento casuale è funzione della soluzione di un rilassamento dell'istanza del problema. Questo fatto è cruciale per dimostrare la garanzia di prestazione dell'algoritmo di approssimazione --- cioè, che per ogni istanza del problema, l'algoritmo restituisce una soluzione che approssima la soluzione ottima per quella specifica istanza . In confronto, le applicazioni del metodo probabilistico in combinatoria mostrano tipicamente l'esistenza di strutture le cui caratteristiche dipendono da altri parametri dell'input. Ad esempio, considera il teorema di Turán , che può essere affermato come "qualsiasi grafo con vertici di grado medio deve avere almeno un insieme indipendente di dimensioni . (Vedi questo per una prova probabilistica del teorema di Turán ). Mentre ci sono grafici per i quali questo limite è stretto, ci sono anche grafi che hanno insiemi indipendenti molto più grandi di .Quindi, la dimensione dell'insieme indipendente mostrato esistere dal teorema di Turán in un grafo può, in generale, essere molto più piccola dell'insieme indipendente massimo per quel grafo.${\displaystyle x}$${\displaystyle n}$${\displaystyle d}$${\displaystyle n/(d+1)}$${\displaystyle n/(d+1)}$

Imposta esempio di copertina

L'esempio seguente illustra come l'arrotondamento casuale può essere utilizzato per progettare un algoritmo di approssimazione per il problema Set Cover .

Correggi qualsiasi istanza di set cover su un universo . ${\displaystyle \langle c,{\mathcal {S}}\rangle}$${\displaystyle {\mathcal {U}}}$

Per il passaggio 1, sia IP il programma lineare intero standard per impostare la copertura per questa istanza.

Per il passaggio 2, sia LP il rilassamento della programmazione lineare di IP e calcolare una soluzione ottimale per LP utilizzando qualsiasi algoritmo di programmazione lineare standard . (Ci vuole tempo polinomiale nella dimensione di input.) ${\displaystyle x^{*}}$

(Le soluzioni ammissibili di LP sono i vettori che assegnano ad ogni insieme un peso non negativo , tale che, per ogni elemento , copre -- il peso totale assegnato agli insiemi che contengono è almeno 1, cioè, ${\displaystyle x}$${\displaystyle s\in {\mathcal {S}}}$${\displaystyle x_{s}}$${\displaystyle e\in {\mathcal {U}}}$${\displaystyle x'}$ ${\displaystyle e}$${\displaystyle e}$

${\displaystyle \sum _{s\ni e}x_{s}\geq 1.}$

La soluzione ottima è una soluzione ammissibile il cui costo ${\displaystyle x^{*}}$

${\displaystyle \sum _{s\in {\mathcal {S}}}c(S)x_{s}^{*}}$

è il più piccolo possibile.)

---

Nota che qualsiasi set di copertura per fornisce una soluzione fattibile (dove per , altrimenti). Il costo di questo è uguale al costo di , cioè ${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle x}$${\displaystyle x_{s}=1}$${\displaystyle s\in {\mathcal {C}}}$${\displaystyle x_{s}=0}$${\displaystyle {\mathcal {C}}}$${\displaystyle x}$

${\displaystyle \sum _{s\in {\mathcal {C}}}c(s)=\sum _{s\in {\mathcal {S}}}c(s)x_{s}.}$

In altre parole, il programma lineare LP è un rilassamento del dato problema di set-cover.

Poiché ha un costo minimo tra le soluzioni possibili per il LP, il costo di è un limite inferiore al costo della copertura dell'insieme ottimale . ${\displaystyle x^{*}}$${\displaystyle x^{*}}$

Passaggio 3: il passaggio dell'arrotondamento casuale

Ecco una descrizione della terza fase: la fase di arrotondamento, che deve convertire la copertura dell'insieme frazionario di costo minimo in una soluzione intera ammissibile (corrispondente a una copertura dell'insieme vero). ${\displaystyle x^{*}}$${\displaystyle x'}$

La fase di arrotondamento dovrebbe produrre un valore che, con probabilità positiva, ha un costo entro un piccolo fattore del costo di . Quindi (poiché il costo di è un limite inferiore del costo della copertura dell'insieme ottimale), il costo di sarà entro un piccolo fattore del costo ottimale. ${\displaystyle x'}$${\displaystyle x^{*}}$${\displaystyle x^{*}}$${\displaystyle x'}$

Come punto di partenza, considera lo schema di arrotondamento più naturale:

Per ogni insieme a sua volta, prendi con probabilità , altrimenti prendi .${\displaystyle s\in {\mathcal {S}}}$${\displaystyle x'_{s}=1}$${\displaystyle \min(1,x_{s}^{*})}$${\displaystyle x'_{s}=0}$

Con questo schema di arrotondamento, il costo previsto dei set scelti è al massimo il costo della copertura frazionata. Questo è buono. Purtroppo la copertura non è buona. Quando le variabili sono piccole, la probabilità che un elemento non sia coperto è di circa ${\displaystyle \sum _{s}c(s)x_{s}^{*}}$${\displaystyle x_{s}^{*}}$${\displaystyle e}$

${\displaystyle \prod _{s\ni e}1-x_{s}^{*}\circa \prod _{s\ni e}\exp(-x_{s}^{*})=\exp { \Big (}-\sum _{s\ni e}x_{s}^{*}{\Big )}\circa \exp(-1).}$

Quindi solo una frazione costante degli elementi sarà coperta nell'aspettativa.

Per coprire ogni elemento con alta probabilità, lo schema di arrotondamento standard prima aumenta le probabilità di arrotondamento di un fattore appropriato . Ecco lo schema di arrotondamento standard: ${\displaystyle x'}$${\displaystyle \lambda >1}$

Fissa un parametro . Per ogni set a turno,${\displaystyle \lambda \geq 1}$${\displaystyle s\in {\mathcal {S}}}$

prendi con probabilità , altrimenti prendi .${\displaystyle x'_{s}=1}$${\displaystyle \min(\lambda x_{s}^{*},1)}$${\displaystyle x'_{s}=0}$

Aumentare le probabilità di aumenta il costo previsto di , ma rende probabile la copertura di tutti gli elementi. L'idea è di scegliere il più piccolo possibile in modo che tutti gli elementi siano coperti in modo dimostrabile con probabilità diversa da zero. Ecco un'analisi dettagliata. ${\displaystyle \lambda}$${\displaystyle \lambda}$${\displaystyle \lambda}$

---

Lemma (garanzia di approssimazione per schema di arrotondamento)

Correggi . Con probabilità positiva, lo schema di arrotondamento restituisce al massimo una copertura fissa di costo (e quindi di costo moltiplicato per il costo della copertura fissa ottimale).${\displaystyle \lambda =\ln(2|{\mathcal {U}}|)}$${\displaystyle x'}$${\displaystyle 2\ln(2|{\mathcal {U}}|)c\cdot x^{*}}$${\displaystyle O(\log |{\mathcal {U}}|)}$

(Nota: con cautela si può ridurre a .) ${\displaystyle O(\log |{\mathcal {U}}|)}$${\displaystyle \ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)}$

Prova

L'output dello schema di arrotondamento casuale ha le proprietà desiderate purché non si verifichi nessuno dei seguenti eventi "cattivi": ${\displaystyle x'}$

1. il costo di supera , o${\displaystyle c\cdot x'}$${\displaystyle x'}$${\displaystyle 2\lambda c\cdot x^{*}}$
2. per alcuni elementi , non riesce a coprire .${\displaystyle e}$${\displaystyle x'}$${\displaystyle e}$

L'aspettativa di ciascuno è al massimo . Per linearità dell'aspettativa , l'aspettativa di è al massimo . Quindi, per la disuguaglianza di Markov , la probabilità del primo evento negativo di cui sopra è al massimo . ${\displaystyle x'_{s}}$${\displaystyle \lambda x_{s}^{*}}$${\displaystyle c\cdot x'}$${\displaystyle \sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}}$${\displaystyle 1/2}$

Per i rimanenti eventi negativi (uno per ogni elemento ), si noti che, poiché per ogni dato elemento , la probabilità che non viene coperta è ${\displaystyle e}$${\displaystyle \sum _{s\ni e}x_{s}^{*}\geq 1}$${\displaystyle e}$${\displaystyle e}$

${\displaystyle {\begin{allineato}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s} ^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{aligned}}}$

(Questo usa la disuguaglianza , che è rigorosa per .) ${\displaystyle 1+z\leq e^{z}}$${\displaystyle z\neq 0}$

Pertanto, per ciascuno degli elementi, la probabilità che l'elemento non sia coperto è inferiore a . ${\displaystyle |{\mathcal {U}}|}$${\displaystyle 1/(2{\mathcal {U}})}$

Per l' ingenua unione vincolata , la probabilità che si verifichi uno degli eventi negativi è inferiore a . Quindi, con probabilità positiva non ci sono eventi negativi ed è al massimo una copertura fissa del costo . QED ${\displaystyle 1+|{\mathcal {U}}|}$${\displaystyle 1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1}$${\displaystyle x'}$${\displaystyle 2\lambda c\cdot x^{*}}$

Derandomizzazione con il metodo delle probabilità condizionate

Il lemma sopra mostra l' esistenza di una copertura fissa del costo ). In questo contesto il nostro obiettivo è un algoritmo di approssimazione efficiente, non solo una prova di esistenza, quindi non abbiamo finito. ${\displaystyle O(\log(|{\mathcal {U}}|)c\cdot x^{*}}$

Un approccio sarebbe quello di aumentare un po', quindi mostrare che la probabilità di successo è almeno, diciamo, 1/4. Con questa modifica, è sufficiente ripetere il passaggio di arrotondamento casuale alcune volte per garantire un esito positivo con alta probabilità. ${\displaystyle \lambda}$

Tale approccio indebolisce il rapporto di approssimazione. Successivamente descriviamo un approccio diverso che produce un algoritmo deterministico che è garantito per corrispondere al rapporto di approssimazione della prova di esistenza sopra. L'approccio è chiamato il metodo delle probabilità condizionate .

L'algoritmo deterministico emula lo schema di arrotondamento randomizzato: considera a turno ogni insieme e sceglie . Ma invece di fare ogni scelta casualmente basata su , fa la scelta in modo deterministico , in modo da mantenere la probabilità condizionata di fallimento, date le scelte finora, al di sotto di 1 . ${\displaystyle s\in {\mathcal {S}}}$${\displaystyle x'_{s}\in \{0,1\}}$${\displaystyle x^{*}}$

Limitare la probabilità condizionata di fallimento

Vogliamo essere in grado di impostare ciascuna variabile a turno in modo da mantenere la probabilità condizionata di fallimento al di sotto di 1. Per fare ciò, abbiamo bisogno di un buon limite alla probabilità condizionata di fallimento. Il limite verrà perfezionando la prova di esistenza originale. Tale prova limita implicitamente la probabilità di fallimento dall'aspettativa della variabile casuale ${\displaystyle x'_{s}}$

${\displaystyle F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|}$,

dove

${\displaystyle {\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \ }}}$

è l'insieme degli elementi lasciati scoperti alla fine.

La variabile casuale può sembrare un po' misteriosa, ma rispecchia la prova probabilistica in modo sistematico. Il primo termine in deriva dall'applicazione della disuguaglianza di Markov per limitare la probabilità del primo evento negativo (il costo è troppo alto). Contribuisce almeno 1 a se il costo di è troppo alto. Il secondo termine conta il numero di eventi negativi del secondo tipo (elementi scoperti). Contribuisce almeno 1 a se lascia scoperto un elemento. Quindi, in ogni risultato in cui è minore di 1, deve coprire tutti gli elementi e avere un costo che soddisfi il limite desiderato dal lemma. In breve, se il passaggio di arrotondamento fallisce, allora . Ciò implica (per la disuguaglianza di Markov ) che è un limite superiore alla probabilità di fallimento. Si noti che l'argomento di cui sopra è già implicito nella dimostrazione del lemma, che mostra anche per calcolo che . ${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$${\displaystyle x'}$${\displaystyle F}$${\displaystyle x'}$${\displaystyle F}$${\displaystyle x'}$${\displaystyle F\geq 1}$${\displaystyle E[F]}$${\displaystyle E[F]<1}$

Per applicare il metodo delle probabilità condizionate, è necessario estendere l'argomento per limitare la probabilità condizionata di fallimento man mano che procede l'arrotondamento. Di solito, questo può essere fatto in modo sistematico, anche se può essere tecnicamente noioso.

Quindi, che dire della probabilità condizionata di fallimento mentre il passaggio di arrotondamento scorre gli insiemi? Poiché in ogni risultato in cui l'arrotondamento fallisce, per la disuguaglianza di Markov , la probabilità condizionata di fallimento è al massimo l' aspettativa condizionata di . ${\displaystyle F\geq 1}$${\displaystyle F}$

Successivamente calcoliamo l'aspettativa condizionata di , proprio come abbiamo calcolato l'aspettativa incondizionata di nella dimostrazione originale. Considera lo stato del processo di arrotondamento alla fine di alcune iterazioni . Lasciate indicare i set considerate finora (i primi set in ). Puoi indicare il (parzialmente assegnato) vettore (quindi è determinato solo se ). Per ogni set , lasciare che denotano la probabilità con cui verrà impostato su 1. Sia contenere gli elementi non ancora coperti. Allora l'aspettativa condizionata di , date le scelte fatte finora, cioè date , è ${\displaystyle F}$${\displaystyle F}$${\displaystyle}$${\displaystyle S^{(t)}}$${\displaystyle}$${\displaystyle {\mathcal {S}}}$${\displaystyle x^{(t)}}$${\displaystyle x'}$${\displaystyle x_{s}^{(t)}}$${\displaystyle s\in S^{(t)}}$${\displaystyle s\not \in S^{(t)}}$${\displaystyle p_{s}=\min(\lambda x_{s}^{*},1)}$${\displaystyle x'_{s}}$${\displaystyle {\mathcal {U}}^{(t)}}$${\displaystyle F}$${\displaystyle x^{(t)}}$

${\displaystyle E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\ mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

Nota che viene determinato solo dopo l'iterazione . ${\displaystyle E[F|x^{(t)}]}$${\displaystyle}$

Mantenere la probabilità condizionata di fallimento al di sotto di 1

Per mantenere la probabilità condizionata di fallimento inferiore a 1, è sufficiente mantenere l'aspettativa condizionata inferiore a 1. Per fare ciò, è sufficiente mantenere l'aspettativa condizionata di dall'aumento. Questo è ciò che farà l'algoritmo. Verrà impostato in ogni iterazione per garantire che ${\displaystyle F}$${\displaystyle F}$${\displaystyle x'_{s}}$

${\displaystyle E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\ leq E[F|x^{(0)}]<1}$

(dove ). ${\displaystyle m=|{\mathcal {S}}|}$

Nel esima iterazione, come può l'insieme di algoritmi per garantire che ? Si scopre che può semplicemente essere impostato in modo da ridurre al minimo il valore risultante di . ${\displaystyle}$${\displaystyle x'_{s'}}$${\displaystyle E[F|x^{(t)}]\leq E[F|S^{(t-1)}]}$${\displaystyle x'_{s'}}$${\displaystyle E[F|x^{(t)}]}$

Per capire perché, concentrati sul momento in cui inizia l' iterazione . In quel momento, è determinato, ma non è ancora determinato --- può assumere due possibili valori a seconda di come è impostato nell'iterazione . Lasciate che denotano il valore di . Siano e , denotano i due possibili valori di , a seconda che sia impostato rispettivamente su 0 o 1. Per definizione di aspettativa condizionata, ${\displaystyle}$${\displaystyle E[F|x^{(t-1)}]}$${\displaystyle E[F|x^{(t)}]}$${\displaystyle x'_{s'}}$${\displaystyle}$${\displaystyle E^{(t-1)}}$${\displaystyle E[F|x'^{(t-1)}]}$${\displaystyle E_{0}^{(t)}}$${\displaystyle E_{1}^{(t)}}$${\displaystyle E[F|x^{(t)}]}$${\displaystyle x'_{s'}}$

${\displaystyle E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}= 1]E_{1}^{(t)}.}$

Poiché una media ponderata di due quantità è sempre almeno il minimo di queste due quantità, ne segue che

${\displaystyle E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).}$

Pertanto, l'impostazione in modo da ridurre al minimo il valore risultante di garantirà che . Questo è ciò che farà l'algoritmo. ${\displaystyle x'_{s'}}$${\displaystyle E[F|x^{(t)}]}$${\displaystyle E[F|x^{(t)}]\leq E[F|x^{(t-1)}]}$

In dettaglio, cosa significa questo? Considerata in funzione di (con tutte le altre quantità fissate) è una funzione lineare di , e il coefficiente di in tale funzione è ${\displaystyle x'_{s'}}$${\displaystyle E[F|x^{(t)}]}$${\displaystyle x'_{s'}}$${\displaystyle x'_{s'}}$

${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{ t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

Pertanto, l'algoritmo dovrebbe essere impostato su 0 se questa espressione è positiva e su 1 in caso contrario. Questo dà il seguente algoritmo. ${\displaystyle x'_{s'}}$

Algoritmo di arrotondamento casuale per set cover set

input: sistema di insieme , universo , vettore di costo${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\displaystyle c}$

output: set cover (una soluzione al programma lineare intero standard per set cover) ${\displaystyle x'}$

---

1. Calcolare una copertura dell'insieme frazionario di costo minimo (una soluzione ottimale per il rilassamento LP).${\displaystyle x^{*}}$
2. Lascia . Lascia per ciascuno .${\displaystyle \lambda \leftarrow \ln(2|{\mathcal {U}}|)}$${\displaystyle p_{s}\leftarrow \min(\lambda x_{s}^{*},1)}$${\displaystyle s\in {\mathcal {S}}}$
3. Per ogni fare: ${\displaystyle s'\in {\mathcal {S}}}$
   1. Lascia . ( contiene gli insiemi non ancora decisi.)${\displaystyle {\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}}$${\displaystyle {\mathcal {S}}}$
   2. Se    ${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _ {s\in {\mathcal {S}},s\ni e}(1-p_{s})}$

      quindi impostare ,${\displaystyle x'_{s}\leftarrow 0}$

      altrimenti impostare e .${\displaystyle x'_{s}\leftarrow 1}$${\displaystyle {\mathcal {U}}\leftarrow {\mathcal {U}}-s'}$

        ( contiene gli elementi non ancora coperti.)${\displaystyle {\mathcal {U}}}$

4. Ritorno .${\displaystyle x'}$

---

lemma (garanzia di approssimazione per algoritmo)

L'algoritmo di cui sopra restituisce un insieme di copertura del costo al massimo delle volte il costo minimo di qualsiasi copertura (frazionaria) dell'insieme.${\displaystyle x'}$${\displaystyle 2\ln(2|{\mathcal {U}}|)}$

prova

---

L'algoritmo garantisce che l'aspettativa condizionale di , , non aumenti ad ogni iterazione. Poiché questa aspettativa condizionale è inizialmente inferiore a 1 (come mostrato in precedenza), l'algoritmo assicura che l'aspettativa condizionale rimanga inferiore a 1. Poiché la probabilità condizionata di fallimento è al massimo l'aspettativa condizionata di , in questo modo l'algoritmo assicura che la probabilità condizionata di fallimento rimane inferiore a 1. Quindi, alla fine, quando tutte le scelte sono state determinate, l'algoritmo raggiunge un esito positivo. Cioè, l'algoritmo di cui sopra restituisce una copertura di costo fissa al massimo delle volte il costo minimo di qualsiasi copertura di insieme (frazionaria). ${\displaystyle F}$${\displaystyle E[F\,|\,x^{(t)}]}$${\displaystyle F}$${\displaystyle x'}$${\displaystyle 2\ln(2|{\mathcal {U}}|)}$

Osservazioni

Nell'esempio sopra, l'algoritmo è stato guidato dall'aspettativa condizionale di una variabile casuale . In alcuni casi, invece di un'aspettativa condizionale esatta, viene utilizzato un limite superiore (o talvolta un limite inferiore) su alcune aspettative condizionali. Questo è chiamato stimatore pessimistico . ${\displaystyle F}$

Guarda anche

• Metodo delle probabilità condizionate

Riferimenti

• Raghavan, Prabhakar ; Tompson, Clark D. (1987), "Arrotondamento randomizzato: una tecnica per algoritmi dimostrabilmente buoni e prove algoritmiche" , Combinatorica , 7 (4): 365-374, doi : 10.1007/BF02579324 , S2CID  5749936.
• Raghavan, Prabhakar (1988), "Costruzione probabilistica di algoritmi deterministici: approssimazione dei programmi interi di imballaggio", Journal of Computer and System Sciences , 37 (2): 130-143, doi : 10.1016/0022-0000 (88)90003-7.

Ulteriori letture

• Althöfer, Ingo (1994), "Sulle approssimazioni sparse alle strategie randomizzate e alle combinazioni convesse", Algebra lineare e sue applicazioni , 199 : 339-355, doi : 10.1016/0024-3795(94)90357-3 , MR  1274423
• Hofmeister, Thomas; Lefmann, Hanno (1996), "Calcolo approssimazioni sparse deterministicamente", Algebra lineare e le sue applicazioni , 240 : 9-19, doi : 10.1016/0024-3795 (94)00175-8 , MR  1387283
• Lipton, Richard J.; Young, Neal E. (1994), "Semplice strategie per grandi giochi a somma zero con applicazioni alla teoria della complessità", STOC '94: Atti del ventiseiesimo simposio annuale ACM sulla teoria del calcolo , New York, NY: ACM , pp. 734-740, arXiv : cs.cc/0205035 , doi : 10.1145/195058.195447 , ISBN 978-0-89791-663-9, S2CID  7524887