ASD2 - 08 - Algoritmi Approssimanti
Date:
Course Site:
Lecturer: Francesco Pasquale
Table of Contents:
In questa lezione abbiamo introdotto una nuova tecnica che ci permette di affrontare i problemi NP-hard. L'idea questa volta è quella di trovare una soluzione che "approssima" la soluzione ottima.
L'idea è quella di preservare l'efficienza rinunciando all'ottimalità della soluzione trovata. Sia quindi \(\pi\) un generico problema di ottimizzazione. Tale problema può essere formalizzato con la seguente tripla
Input: \(I\)
Soluzione Ammissibile \(S(I)\)
Goal: min/max \(f(S(I))\)
Sia inoltre \(S^*(I)\) una soluzione ottima per l'istanza \(I\), e sia \(OPT(I) := f(S^*(I))\), ovvero \(OPT(I)\) è il costo della soluzione ottima per l'istanza \(I\). Per semplicità possiamo assumere che \(OPT(I)\) sia sempre un intero positivo.
Supponiamo quindi di avere un algoritmo \(\mathcal{A}\) per il nostro problema. Data l'istanza \(I\) il nostro algoritmo trova la soluzione con valore \(\mathcal{A}(I)\). Il rapporto di approssimazione, o in inglese approximation ratio dell'algoritmo \(\mathcal{A}\) è definito in modi diversi a seconda della natura del problema. In particolare troviamo
Per problemi di minimizzazione definiamo
\[\alpha_A := \max_I \frac{\mathcal{A}(I)}{OPT(I)}\]
dunque \(\alpha_A\) misura il fattore con cui la soluzione ritornata dall'algoritmo supera quella ottimale nel caso peggiore.
Per problemi di massimizzazione definiamo
\[\alpha_A := \max_I \frac{OPT(I)}{\mathcal{A}(I)}\]
Per chiarire le idee procediamo con l'analisi di un algoritmo approssimante.
Supponiamo di avere \(m\) macchine e \(n\) tasks, ciascun dei quali richiede un particolare tempo \(t \in \mathbb{N}\). Siamo interessati a schedulare i vari tasks nelle varie macchine in modo da minimizzare il lavoro massimo eseguito da una macchina. Formalizzando troviamo il seguente problema
Input: \(m \in \mathbb{N}\) rappresenta il numero di macchine, mentre gli \(n\) tasks sono caratterizzati da \(n\) interi \(t_1, \ldots t_n \in \mathbb{N}\), dove l'intero \(t_i\) indica il tempo impiegato dall' \(i\) -esimo task.
Soluzione Ammissibile: Una soluzione ammissibile è data da una funzione
\[\sigma: [n] \to [m]\]
che mappa ciascun task \(t_i\) ad una singnola macchina \(\sigma(t_i) \in [m]\), dove con la notazione \([n]\) intendiamo l'insieme nei primi \(n\) naturali, ovvero
\[\forall n \in \mathbb{N}: \,\,\, [n] := \{1, 2, \ldots, n\}\]
Goal: Il nostro obiettivo è quello di minimizzare il \(\text{Makespan}(\sigma)\), definito nel seguente modo
\[\text{Makespan}(\sigma) := \underset{1 \leq j \leq m}{\max} \Big\{ \sum\limits_{\substack{1 \leq i \leq n: \\ \sigma(i) = j}} t_i\Big\}\]
Per risolvere tale problema possiamo utilizzare il seguente algoritmo greedy, che assegna il carico \(t_i\) alla macchina che in quel momento ha meno carico totale
L'analisi dell'algoritmo verrà fatta in due modi diversi, uno non considerando il fatto che i tasks sono ordinati, e l'altro consideranto l'ordine dei tasks.
Sia \(OPT\) la soluzione ottima del problema sull'istanza \(I\), e sia \(S_{\mathcal{A}}\) la soluzione ritrovata dal nostro algoritmo greedy. Come è solito fare quando si vuole dimostrare un risultato di approssimazione per problemi di minimizzazione, riportiamo i seguenti lower bounds alla soluzione ottima
\(OPT \geq t_{max} := \max_i t_i\)
\(OPT \geq \frac{1}{m} \sum\limits_{i = 1}^n t_i\)
Il primo lower bound è ovvio, mentre il secondo vale in quanto, se così non fosse, dato che fissata una particolare istanza tutte le altre macchine hanno un carico minore di \(OPT\) in totale avremmo un carico di lavoro maggiorato strettamente da \(m \cdot OPT < \sum_{i = 1}^n t_i\) il che è un assurdo.
Definiamo \(L_j^t\) come il carico di lavoro della macchina \(j\) alla \(t\) -esima iterazione, e \(L_j\) come il carico della macchina \(j\) alla fine della computazione.
Sia \(j\) la macchina che alla fine ha il maggior carico, e sia \(t_i\) l'ultimo task assegnato alla macchina \(j\). Troviamo che
\[S_{\mathcal{A}} = L_j = L_j^i + t_i \implies L_j^i = L_j - t_i\]
Utilizzando la regola greedy dell'algoritmo possiamo dire che, poiché al passo \(i\) il task \(t_i\) è stato assegnato alla macchina \(j\), allora, al passo \(i\), il carico della macchina \(j\) era il carico più piccolo di tutte le macchine. In formula
\[\forall h \in [m]: \,\,\,\, L_j^i = L_j - t_i \leq L_h^i\]
Sapendo inoltre che i carichi possono solo aumentare, ovvero che \(L_h^i \leq L_h\) per ogni \(h \in [m]\), troviamo
\[\forall h \in [m]: \,\,\,\, L_j^i = L_j - t_i \leq L_h\]
espandendo questa formula troviamo quindi il seguente sistema
\[\begin{cases} L_j - t_i \leq L_1 \\ L_j - t_i \leq L_2 \\ \vdots \\ L_j - t_i \leq L_m \\ \end{cases}\]
e moltiplicando tra loro queste disuguaglianze troviamo
\[m(L_j - t_i) \leq \sum\limits_{h = 1}^m L_h = \sum\limits_{h = 1}^n t_h \implies L_j - t_i \leq \frac{1}{m} \sum\limits_{h=1}^n t_h\]
Infine, utilizzando i lower bounds menzionati all'inizio dell'analisi, otteniamo
\[\begin{split} S_{\mathcal{A}} = L_j &\leq \frac{1}{m} \sum\limits_{h = 1}^n t_h + t_i \\ &\leq \frac{1}{m} \sum\limits_{h = 1}^n t_h + t_{max} \\ &\leq OPT + OPT \\ &= 2OPT \\ \end{split}\]
e quindi
\[S_{\mathcal{A}} \leq 2 OPT \iff \frac{S_{\mathcal{A}}}{OPT} = 2\]
ovvero il nostro algoritmo ottiene una \(2\) approssimazione dell'ottimo.
Osservazione: Il fatto che riusciamo a dimostrare che la soluzione ritornata da un certo algoritmo ottiene un fattore di approssimazione \(\alpha\) rispetto alla soluzione ottima non esclude il fatto che magari le soluzioni ritornate dall'algoritmo in realtà hanno un fattore di approssimazione migliore. Ad esempio nel nostro caso il vero fattore di approssimazione dell'algoritmo è \(3/2\), e non \(2\). Una analisi più dettagliata è riportata a seguire.
L'analisi è praticamente identica a quella di prima, con l'unica differenza che, essendo i tasks \(t_i\) ordinati \(t_1 \geq t_2 \geq \ldots t_n\), abbiamo che
\[OPT \geq 2 t_{m+1}\]
Infatti, assumendo che \(n > m\), in quanto se \(n \leq m\) l'algoritmo trova sicuramente l'ottimo \(OPT = t_{max}\), abbiamo che durante le prime \(m\) iterazioni l'algoritmo seleziona sempre una macchina vuota per assegnarli il task. Durante la \((m+1)\) -esima iterazione poi, assegna il task \(t_{m+1}\) alla macchina a cui aveva assegnato il task \(t_m\), che era il più breve tra tutti quelli assegnati. Ma allora esisterà sempre una macchina con almeno i task \(t_m\) e \(t_{m+1}\), e quindi
\[OPT \geq t_m + t_{m+1} \geq t_{m+1} + t_{m+1} = 2 t_{m+1}\]
Infine, assumendo \(i \geq m+1\), possiamo maggiorare il valore del task \(t_i\) dell'analisi precedente con
\[t_i \leq t_{m+1} \leq \frac{OPT}{2} \implies t_i \leq \frac{OPT}{2}\]
Nell'espressione finale otteniamo quindi
\[S_{\mathcal{A}} \leq \frac{1}{m} \sum\limits_{h = 1}^n t_h + t_i \leq OPT + \frac{1}{2} OPT = \frac{3}{2} OPT\]
dunque
\[\frac{S_{\mathcal{A}}}{OPT} = \frac{3}{2}\]
Andiamo adesso a vedere un problema che può essere approssimato arbitrariamente. Prima però introduciamo qualche definizione
Def: Un algoritmo è detto approximation schema per un problema di ottimizzazione \(\Pi\) con funzione obiettivo \(f_{\Pi}\) se prende in input una coppia \((I, \epsilon)\) con \(I\) istanza del problema e \(\epsilon > 0\) parametro di errore, e ritorna una soluzione \(s\) tale che
Se \(\Pi\) è un problema di minimizzazione allora
\[f_{\Pi}(I, s) \leq (1 + \epsilon) \cdot OPT\]
Se \(\Pi\) è un problema di massimizzazione allora
\[f_{\Pi}(I, s) \geq (1 - \epsilon) \cdot OPT\]
Def: Uno schema di approssimazione \(\mathcal{A}\) è detto polynomial time approximation schema, o PTAS, se per ogni \(\epsilon > 0\) fissato, il running time è limitato da un polinomio nella grandezza dell'input.
Notiamo che un PTAS potrebbe avere una complessità esponenziale rispetto a \(1/\epsilon\). In questi casi potrebbe diventare veramente difficile avvicinarsi di molto alla soluzion corretta. Entra quindi in gioco la classe FPTAS.
Def: Uno schema di approssimazione \(\mathcal{A}\) è detto fully polynomial time approximation schema, o FPTAS, se l'algoritmo è polinomialmente limitato sia nella grandezza dell'istanza \(I\) e sia rispetto a \(1/\epsilon\).
Il problema dello zaino, o knapsack in inglese, può essere formalizzato come segue
Input: L'input è dato da una sequenza di \(n\) coppie \((v_i, w_i) \in \mathbb{N} \times \mathbb{N}\) e da un intero \(W \in \mathbb{N}\). Per ogni coppia il numero \(v_i\) rappresenta il valore dell'oggetto, mentre il numero \(w_i\) rappresenta il peso dell'oggetto. Il numero \(W\) invece rappresenta il peso massimo che non dobbiamo superare.
Soluzioni Ammissibili: Una soluzione è un sottoinsieme di \([n]\), che contiene gli indici di tutte le coppie che prendiamo e deve essere tale che
\[\sum\limits_{i \in S} w_i \leq W\]
ovvero non dobbiamo superare il peso massimo.
Goal: Il nostro obiettivo è quello di massimizzare il valore di una soluzione \(S\), dove il valore della soluzione è la somma del valore degli oggetti che abbiamo scelto, ovvero
\[val(S) := \sum\limits_{i \in S} v_i\]
Come prima cosa andiamo a risolvere il problema del knapsack con un algoritmo di programmazione dinamica. Come al solito quindi, definiamo i nostri sottoproblemi. In questo caso per ogni \(i = 1, \ldots, n\) e per ogni \(k = 0, \ldots, W\) definiamo
\[\begin{split} OPT(i, k) := &\text{ valore massimo ottenibili dagli oggetti } 1, \ldots, i \\ &\,\text{ con peso massimo } k \\ \end{split}\]
notiamo le seguenti formule
Per ogni \(k = 0, \ldots, W\)
\[OPT(0, k) = 0\]
Per ogni \(i = 0, \ldots, n\)
\[OPT(i, 0) = 0\]
Per i restanti casi invece vale la seguente formula generale
\[OPT(i, k) = \begin{cases} OPT(i-1, k) &, \,\, w_i > k \\ \max\{OPT(i-1, k), \,\, w_i + OPT(i-1, k-w_i)\} &, \,\, \text{ else } \\ \end{cases}\]
Possiamo quindi utilizzare il seguente algoritmo per risolvere il problema
Notiamo che la complessità dell'algoritmo è \(O(n \cdot W)\), che è una complessità pseudopolinomiale nel senso che è polinomiale rispetto al valore numerico \(W\), ma non rispetto alla lunghezza dell'input, in quanto il numero di bit necessari per memorizzare il numero \(W\) è \(O(\log W)\).
Riportiamo poi qualche considerazione di carattere generale
Un approccio greedy potrebbe ordinare gli oggetti per il rapporto \(v_i/w_i\).
Nell'approccio dinamico fatto vedere, al posto di mantenere l'intera tabella contenete i vari \(OPT(i, k)\) mi posso semplicemente mantenere un vettore colonna per calcolarmi la colonna successiva a quella a cui sono arrivato.
È possibile definire un algoritmo di programmazione dinamica che risolve il knapsack con complessità \(O(n V_s)\), dove \(V_s = \sum\limits_{i = 1}^n v_i\).
Consideriamo l'algoritmo pseudo-polinomiale che risolve knapsack in \(O(n \cdot V_s)\), con \(V_s = \sum_{i = 1}^n v_i\). L'idea è quella di rendere l'algoritmo polinomiale semplicemente scalando i valori \(v_i\) per una data costante \(b\). In particolare quindi al posto di avere \(v_i\) come valore dell' \(i\) -esimo oggetto, consideriamo il valore scalato \(\hat{v_i} := \lfloor \frac{v_i}{b} \rfloor\). Ovviamente, visto che \(v_i/b\) generalmente non è un intero, prendendo la parte intera inferiore \(\lfloor v_i/b \rfloor\) introduciamo un errore di approssimazione.
Sia \(\hat{S_A} \subseteq [n]\) una soluzione ottima per il problema con i valori scalati \(\hat{v_i}\), e sia \(S^* \subseteq [n]\) una soluzione ottima per il problema originario. Allora valgono le seguenti disuguaglianze
Dato che \(\hat{S_A}\) è la soluzione ottima per l'istanza con i pesi scalati, per definizione troviamo
\[\sum\limits_{i \in \hat{S_A}} \hat{v_i} \geq \sum\limits_{i \in S^*} \hat{v_i}\]
In generale poi vale
\[\frac{v_i}{b} - 1 \leq \hat{v_i} = \lfloor \frac{v_i}{b} \rfloor \leq \frac{v_i}{b}\]
Troviamo quindi da un lato
\[\sum\limits_{i \in \hat{S_A}} \hat{v_i} \leq \frac{1}{b} \sum\limits_{i \in \hat{S_A}} v_i\]
e dall'altro lato
\[\begin{split} \sum\limits_{i \in \hat{S_A}} \hat{v_i} \geq \sum\limits_{i \in S^*} \hat{v_i} &\geq \sum\limits_{i \in S^*} \Big(\frac{v_i}{b} - 1 \Big) \\ &\geq \frac{1}{b} \sum\limits_{i \in S^*} v_i - |S^*| \\ &\geq \frac{1}{b} \sum\limits_{i \in S^*} v_i - n \end{split}\]
Combinando queste due disuaglianze tra loro troviamo
\[\frac{1}{b} \sum\limits_{i \in S^*} v_i - n \leq \frac{1}{b} \sum\limits_{i \in \hat{S_A}} v_i\]
il che implica
\[\sum\limits_{i \in \hat{S_A}} v_i \geq \sum\limits_{i \in S^*} v_i - nb\]
Ora, dato un \(\epsilon > 0\) posso fissare \(b\) in modo tale che
\[\sum\limits_{i \in \hat{S_A}} v_i \geq (1 - \epsilon) \sum\limits_{i \in S^*} v_i\]
per fare questo devo avere avere \(nb \leq \epsilon \sum_{i \in S^*} v_i\). Così facendo infatti trovo
\[\sum\limits_{i \in \hat{S_A}} v_i \geq \sum\limits_{i \in S^*} v_i - nb \geq \sum\limits_{i \in S^*} v_i - \epsilon \cdot \sum\limits_{i \in S^*} v_i = (1 - \epsilon) \sum\limits_{i \in S^*} v_i\]
posso quindi definire \(b\) come \(b := \frac{V_{max}}{n}\) con \(V_{max} = \max_i v_i\). Infatti, assumendo che \(w_i \leq W\) per ogni \(i\), allora \(\sum_{i \in S^*} v_i \geq V_{max}\).
Avendo scelto \(b\) come fattore di scollamento troviamo quindi che l'oggetto \(i\) viene scalato nel seguente modo
\[\hat{v_i} := \Big\lfloor \frac{n v_i}{\epsilon V_{max}} \Big\rfloor\]
Inoltre, utilizzando l'algoritmo di programmazione dinamica con complessità \(O(nV_s)\), troviamo che
Il valore della soluzione trovata è
\[val(\hat{A_s}) \geq (1 - \epsilon) val(S^*)\]
ovvero abbiamo un fattore di approssimazione di \(1-\epsilon\).
La complessità dell'algoritmo è
\[O(nV_s) = O(n^2 V_{max}) = O\Big(\frac{n^3}{\epsilon}\Big)\]
Non tutti i problemi possono essere approsimati con un fattore \(\alpha\) costante. Segue un esempio di un problema del genere
Il Travelling salesman problem (TSP) può essere formalizzato come segue
Input:
\(V = \{v_1, \ldots, v_n\}\) insieme finito.
\(w\) funzione di pesaura degli archi, \(w(u, v) \in \mathbb{N}\).
Soluzione Ammissibile: \(S = (v_0, \ldots, v_n)\) permutazione di \(V\)
Goal: \(\min COST(S)\), con
\[COST(S) = \sum\limits_{i = 0}^{n-1} w(v_i, v_{i+1})\]
Limitando le istanze del TSP, e in particolare richiedendo che \(w\) sia una distanza e dunque che rispetti la disuguaglianza triangolare, siamo in grado di definire un algoritmo \(2\) approssimante.
Supponiamo quindi di avere un ciclo di archi ottimale che visita tutti i nodi di \(V\). Notiamo che rimuovendo un arco da tale ciclo otteniamo uno spanning tree. Ma quindi abbiamo
\[\text{TSP Cost} \geq \text{Cost of the path} \geq \text{MST Cost}\]
A partire da un MST poi, semplicemente percorrendo al massimo due vogli ogni arco riusciamo a trovare un TSP approssimato di un fattore due al massimo. Infine, al posto di andare a revisitare una città già visitata possiamo andare nella nuova città e, utilizzando la disuguaglianza triangolare, notiamo che questa modifica non può peggiorare il tour.
Vale il seguente teorema
Teorema: Il problema di \(\alpha\) approssimare il TSP è un problema NP-hard.
Dimostrazione: Effettuiamo una riduzione dal problema ciclo hamiltoniano (HC).
L'idea è quella di passare da istanze \(I\) di HC a istanze \(f(I)\) di \(\alpha\) APPROX TSP in modo tale che a seconda del risultato ottenuto per \(f(I)\), ovvero a seconda del costo del tour minimo, riesco a capire se esiste o meno un ciclo Hamiltoniano in \(I\).
Formalmente costruiamo la seguente riduzione \(f:I_{HC} \to I_{\alpha-TSP}\) con
\[f(G = (V, E)) = (G' = (V', E'), w)\]
tale che
\(V' := V\)
\(E' := V \times V\)
\(C \in \mathbb{N}\)
\(\forall e' \in E': \,\, w(e') = \begin{cases} 1 &,\,\,\, e' \in E \\ C &,\,\,\, e' \not \in E \end{cases}\)
Notiamo che la riduzione può essere calcolata in \(O(|V|^2)\) ed è quindi polinomiale. Possiamo vedere che
\[Cost_{OPT}(f(G)) = n \iff G \text{ contiene un ciclo Hamiltoniano}\]
Infatti, se il costo ottimale di \(f(G)\) è \(n\), allora il tour ottimale in \(f(G)\) deve necessariamente passare in archi di \(G\), in quanto altrimenti avrebbe un costo di almeno \(C + (n-1)\), e supponendo \(C > 1\), questo sarebbe strettamente maggiore di \(n\). Dunque, se \(G\) contiene un ciclo Hamiltoniano, allora per costruzione abbiamo che \(Cost_{OPT}(f(G)) = n\), in quanto tutti gli altri tour che utilizzano archi non di \(G\) vengono a costare più di \(n\).
Ricordiamo però che noi sappiamo solo \(\alpha\) approssimare la soluzione ottima del TSP. Quindi, se il costo ottimale di \(f(G)\) è \(n\), il nostro algoritmo ci darà un valroe compreso tra \(n\) e \(\alpha n\). L'idea è quindi scegliere \(C\) in modo tale che appena tocchiamo un arco non del grafo la soluzione supera il valore \(n \alpha\). Un possibile valore è \(C := n \alpha\).
Abbiamo quindi la seguente proprietà
\[G \in I_{HC} \iff Cost_{OPT}(f(G)) \leq n \alpha\]
Infatti,
\((\Rightarrow)\): Se \(G \in I_{HC}\), allora esiste un ciclo hamiltoniano in \(G\), e quindi \(cost_{OPT}(f(G)) = n\). Infine, avendo una \(\alpha\) approssimazione del TSP, possiamo dire che
\[Cost_{\alpha}(f(G)) \leq \alpha \cdot Cost_{OPT}(f(G)) = \alpha n\]
\((\Leftarrow)\): Se \(Cost_{\alpha}(f(G)) \leq n \alpha\), allora abbiamo necessariamente utilizzato tutti gli archi di \(G\). Ma allora esiste un ciclo Hamiltoniano in \(G\).