Un algoritmo $\mathscr{A}$ per un problema di massimo (valore ottimo $z(I)$) ha errore relativo $\frac{z(I)-\mathscr{A}(I)}{z(I)}$ al più $\varepsilon=\frac14$. Qual è la sua garanzia relativa $\alpha$, intesa come limite sul rapporto $z(I)/\mathscr{A}(I)$?
$\alpha=\frac43$
$\alpha=\frac54$
$\alpha=\frac34$
$\alpha=4$
Spiegazione. Per un problema di massimo $z-\mathscr{A}\le\varepsilon z$ dà $z/\mathscr{A}\le\frac{1}{1-\varepsilon}=\frac43$; per un problema di minimo si avrebbe $1+\varepsilon=\frac54$.
Per un problema di minimo, un'euristica trova $\mathscr{A}(I)=12$ e il valore ottimo è $z(I)=10$. Quanto valgono il rapporto di prestazione $\mathscr{A}(I)/z(I)$ e l'errore relativo $\frac{\mathscr{A}(I)-z(I)}{z(I)}$?
$\frac56$ e $20\%$
$\frac65$ e $2$
$\frac56$ e $16{,}7\%$
$\frac65$ e $20\%$
Spiegazione. Per il minimo il rapporto è $\mathscr{A}(I)/z(I)=\frac{12}{10}$, sempre almeno $1$; l'errore relativo è $\frac{12-10}{10}=20\%$; l'errore additivo è $2$.
Uno schema di approssimazione riceve un'istanza e un $\varepsilon>0$ e restituisce una soluzione con errore relativo al più $\varepsilon$. Quale affermazione su PTAS e FPTAS è corretta?
In un PTAS e in un FPTAS il tempo è polinomiale per ogni $\varepsilon$ fissato, e in nessuno dei due in $\frac1\varepsilon$
Un tempo $O(n^{1/\varepsilon})$ è polinomiale sia nella dimensione sia in $\frac1\varepsilon$, quindi dà un FPTAS
In un PTAS il tempo è polinomiale per ogni $\varepsilon$ fissato; in un FPTAS è polinomiale anche in $\frac1\varepsilon$
In un PTAS il tempo è polinomiale anche in $\frac1\varepsilon$; in un FPTAS lo è solo per ogni $\varepsilon$ fissato
Spiegazione. Un tempo come $O(n^{1/\varepsilon})$ è polinomiale per $\varepsilon$ fissato (PTAS) ma non in $\frac1\varepsilon$; un FPTAS, come $O(n^2/\varepsilon)$, è polinomiale in entrambi.
Per un problema di minimo, la garanzia relativa di un algoritmo $\mathscr{A}$ è una costante $\alpha$ con $\mathscr{A}(I)\le\alpha\,z(I)$ per ogni istanza $I$. Su una certa istanza $\mathscr{A}$ ha rapporto $\mathscr{A}(I)/z(I)=\frac32$. Che cosa dimostra questa istanza?
Che ogni costante maggiore di $\frac32$ è una garanzia relativa di $\mathscr{A}$
Che nessuna costante minore di $\frac32$ è una garanzia relativa di $\mathscr{A}$
Che $\frac32$ è una garanzia relativa di $\mathscr{A}$, valida per ogni istanza
Che il rapporto di $\mathscr{A}$ nel caso peggiore è esattamente $\frac32$
Spiegazione. Un'istanza dà solo un lower bound su $r(\mathscr{A})$: per dimostrare che $\frac32$ è una garanzia serve una dimostrazione valida per ogni istanza.
Per un problema di massimo, il rapporto di prestazione di un algoritmo $\mathscr{A}$ sull'istanza $I$ è $z(I)/\mathscr{A}(I)$, con $z(I)$ valore ottimo. Un'euristica per lo zaino trova $\mathscr{A}(I)=16$ su un'istanza con $z(I)=20$. Quanto vale il rapporto?
$4$
$\frac{9}{5}$
$\frac54$
$\frac45$
Spiegazione. $20/16=\frac54\ge 1$. Nei problemi di massimo si mette l'ottimo al numeratore, così il rapporto è sempre almeno $1$ come nei problemi di minimo; $\frac45$ è il rapporto capovolto.
Il rapporto di prestazione nel caso peggiore $r(\mathscr{A})$ è l'estremo superiore dei rapporti di prestazione di $\mathscr{A}$ su tutte le istanze, e $\mathscr{A}$ è una $\alpha$-approssimazione se il rapporto è al più $\alpha$ su ogni istanza. Quale affermazione è corretta?
$r(\mathscr{A})$ è sempre raggiunto da qualche istanza
$\mathscr{A}$ è una $\alpha$-approssimazione se e solo se $\alpha\ge r(\mathscr{A})$
$\mathscr{A}$ è una $\alpha$-approssimazione se e solo se $\alpha=r(\mathscr{A})$
$\mathscr{A}$ è una $\alpha$-approssimazione se e solo se $\alpha\le r(\mathscr{A})$
Spiegazione. Ogni rapporto è al più l'estremo superiore, quindi $\alpha=r(\mathscr{A})$ e ogni $\alpha$ maggiore sono garanzie; una costante minore no. L'estremo superiore può essere solo avvicinato, come per $GR^e$ nello zaino.
Per un problema di minimo, $\mathscr{A}$ è un algoritmo con garanzia additiva $\beta$ se $\mathscr{A}(I)-z(I)\le\beta$ per ogni istanza. Un algoritmo per la colorazione dei grafi planari usa al più $5$ colori, e il grafo contiene un triangolo. Quale garanzia additiva si ottiene su questi grafi?
$\beta=2$, perché $\chi(G)\ge 3$
$\beta=5$, il numero di colori usati
$\beta=\frac53$, il rapporto fra colori usati e numero cromatico
$\beta=1$, perché $\chi(G)\le 4$
Spiegazione. Con un triangolo $\chi(G)\ge 3$, e quindi $5-\chi(G)\le 2$. La garanzia additiva misura la differenza, non il rapporto.
Per un problema di minimo, un algoritmo con garanzia additiva $\beta$ soddisfa $\mathscr{A}(I)\le z(I)+\beta$. Che cosa implica per il rapporto di prestazione $\mathscr{A}(I)/z(I)$?
$\mathscr{A}(I)/z(I)\le\beta$ per ogni istanza
$\mathscr{A}(I)/z(I)\ge 1+\beta$ per ogni istanza
Nulla: le due garanzie sono indipendenti
$\mathscr{A}(I)/z(I)\le 1+\beta/z(I)$, che tende a $1$ quando $z(I)$ cresce
Spiegazione. Dividendo per $z(I)>0$ si ottiene $1+\beta/z(I)$: sulle istanze con valore ottimo grande una garanzia additiva è più forte di qualsiasi garanzia relativa costante.
Per un problema di minimo, una $\alpha$-approssimazione soddisfa $\mathscr{A}(I)\le\alpha\,z(I)$ per ogni istanza. Una $2$-approssimazione restituisce una soluzione di valore $30$. Che cosa si sa del valore ottimo $z(I)$?
$30\le z(I)\le 60$
$z(I)\le 15$
$15\le z(I)\le 30$
$z(I)=15$
Spiegazione. La soluzione è ammissibile, quindi $z(I)\le 30$; la garanzia dà $30\le 2z(I)$, cioè $z(I)\ge 15$. La garanzia fornisce un bound duale anche senza un rilassamento.
Uno schema di approssimazione per un problema di massimo è una famiglia di algoritmi $\{\mathscr{A}_\varepsilon\}_{\varepsilon\in(0,1)}$ che, per ogni $\varepsilon$ e ogni istanza, hanno errore relativo $\frac{z(I)-\mathscr{A}_\varepsilon(I)}{z(I)}$ al più $\varepsilon$. Che cosa ci si aspetta del tempo di calcolo al diminuire di $\varepsilon$?
Che diventi esponenziale per ogni $\varepsilon<\frac12$
Che cresca: un errore ammesso più piccolo richiede più tempo
Che diminuisca: con $\varepsilon$ piccolo ci sono meno soluzioni da esaminare
Che resti costante: $\varepsilon$ cambia solo la garanzia
Spiegazione. È naturale che il tempo cresca quando l'errore ammesso diminuisce; PTAS e FPTAS si distinguono proprio per come cresce rispetto a $\frac1\varepsilon$.
Uno schema di approssimazione con $n$ elementi in input e parametro di errore $\varepsilon$ è un FPTAS se il tempo è polinomiale sia nella dimensione dell'istanza sia in $\frac1\varepsilon$. Quale dei seguenti tempi dà un FPTAS?
$O(n^2/\varepsilon)$
$O(n^{1/\varepsilon})$
$O(2^{1/\varepsilon}\,n)$
$O(n^{1/\varepsilon^2})$
Spiegazione. $n^2/\varepsilon$ è un polinomio in $n$ e in $\frac1\varepsilon$: è il tempo del Basic-FPTAS per lo zaino. Gli altri sono polinomiali in $n$ per $\varepsilon$ fissato (PTAS) ma non in $\frac1\varepsilon$.
Un PTAS per un problema ha tempo $O(n^{1/\varepsilon})$ su istanze con $n$ elementi. Come cambia il tempo passando da $\varepsilon=\frac12$ a $\varepsilon=\frac1{10}$?
Da $O(n^2)$ a $O(n^{2/10})$: diminuisce
Resta $O(n^2)$: l'esponente non dipende da $\varepsilon$
Diventa esponenziale in $n$
Da $O(n^2)$ a $O(n^{10})$: polinomiale per ogni $\varepsilon$ fissato, ma con esponente crescente
Spiegazione. Per ogni $\varepsilon$ fissato il tempo è un polinomio in $n$, ma il grado cresce come $\frac1\varepsilon$: per questo non è un FPTAS.
Per un algoritmo euristico $\mathscr{A}$ e un'istanza $I$, $z(I)$ è il valore ottimo e $\mathscr{A}(I)$ il valore euristico, entrambi supposti positivi. Perché si suppone la positività?
Perché ogni problema di ottimizzazione ha valori positivi
Perché $\mathscr{A}(I)$ deve essere uguale a $z(I)$
Perché i valori negativi sono inammissibili
Perché i rapporti $\mathscr{A}(I)/z(I)$ e $z(I)/\mathscr{A}(I)$ siano definiti e significativi
Spiegazione. Le garanzie relative confrontano i due valori con un rapporto: con un valore nullo o di segno diverso il rapporto perderebbe senso.
Il rapporto di prestazione di un algoritmo $\mathscr{A}$ su un'istanza $I$ è $\mathscr{A}(I)/z(I)$ per un problema di minimo e $z(I)/\mathscr{A}(I)$ per un problema di massimo ($z(I)$ = valore ottimo). Quanto vale con $z=40$, $\mathscr{A}=50$ (minimo) e con $z=40$, $\mathscr{A}=32$ (massimo)?
$1.25$ in entrambi i casi
$1.25$ e poi $0.8$
$0.8$ e poi $1.25$
$0.8$ in entrambi i casi
Spiegazione. $50/40=1.25$ e $40/32=1.25$. Con queste definizioni il rapporto è sempre almeno $1$, qualunque sia il verso dell'ottimizzazione.
Negli algoritmi di approssimazione si valuta un'euristica nel caso peggiore, con una garanzia relativa (moltiplicativa) o assoluta (additiva). Che cosa misura la garanzia assoluta?
Il rapporto fra il valore euristico e il valore ottimo
Il tempo di calcolo nel caso peggiore
La differenza fra il valore ottimo e un lower bound
La differenza fra il valore euristico e il valore ottimo
Spiegazione. La garanzia relativa limita un rapporto, quella assoluta l'errore $|\mathscr{A}(I)-z(I)|$, su tutte le istanze.
Un algoritmo per un problema di massimo ha garanzia di prestazione assoluta $k=3$: $z(I)-\mathscr{A}(I)\le3$ su ogni istanza. Su un'istanza con $z(I)=50$, quale valore euristico è garantito?
Almeno $53$
Almeno $150$
Almeno $47$
Almeno $50/3$
Spiegazione. L'errore assoluto è al più $3$: $\mathscr{A}(I)\ge50-3$. $50/3$ confonde la garanzia assoluta con un rapporto.
Se un algoritmo $\mathscr{A}$ restituisce sempre una soluzione ammissibile, che cosa si può dire del suo rapporto di prestazione su ogni istanza?
Può essere negativo
È almeno $1$
È al più $1$
È sempre esattamente $1$
Spiegazione. Una soluzione ammissibile non è mai migliore dell'ottimo: il rapporto (definito per avere l'ottimo «dalla parte giusta») è $\ge1$, con l'uguaglianza solo all'ottimo.
Un algoritmo per un problema di minimo ha $\mathscr{A}(I)\le 2z(I)$ su ogni istanza. Che cosa si può concludere?
È un algoritmo di $2$-approssimazione
È un algoritmo $2$-additivo
Ha errore relativo al più $\frac12$
È uno schema di approssimazione
Spiegazione. $\mathscr{A}(I)/z(I)\le2$ per ogni $I$ è proprio la definizione di $\alpha$-approssimazione con $\alpha=2$; l'errore relativo è al più $1$.
Un algoritmo per un problema di massimo ha $\mathscr{A}(I)\ge\frac12 z(I)$ su ogni istanza. Di quale $\alpha$-approssimazione si tratta?
$\alpha=\frac12$
$\alpha=\frac32$
Nessuna: per i problemi di massimo $\alpha$ è minore di $1$
$\alpha=2$
Spiegazione. Per un problema di massimo si richiede $z(I)/\mathscr{A}(I)\le\alpha$: da $\mathscr{A}(I)\ge\frac12z(I)$ segue $z(I)/\mathscr{A}(I)\le2$. Nel corso $\alpha\ge1$ sempre.
Si dimostra che un algoritmo è una $\frac32$-approssimazione e si trova una famiglia di istanze su cui il rapporto tende a $\frac32$. Che cosa si è mostrato in più?
Che la garanzia $\frac32$ è tight
Che l'algoritmo è ottimo
Che il problema non ha uno schema di approssimazione
Che $r(\mathscr{A})<\frac32$
Spiegazione. Una famiglia di istanze con rapporto che tende ad $\alpha$ impedisce ogni $\alpha'<\alpha$: la garanzia è stretta e $r(\mathscr{A})=\frac32$.
Un problema di massimo ha $z(I)=17$; un algoritmo $2$-additivo può restituire, su questa istanza, quali valori?
Solo $15$
Ogni valore fra $\frac{17}{2}$ e $17$
Ogni valore fra $15$ e $17$
Ogni valore fra $17$ e $19$
Spiegazione. Per un problema di massimo la garanzia additiva è $z(I)-\mathscr{A}(I)\le2$, e $\mathscr{A}(I)\le z(I)$: quindi $15\le\mathscr{A}(I)\le17$.
Che cosa è uno schema di approssimazione per un problema $\mathscr{P}$?
Un algoritmo esatto pseudo-polinomiale
Una famiglia di istanze su cui una garanzia è stretta
Una famiglia di algoritmi $\mathscr{A}_\varepsilon$
Un solo algoritmo con errore relativo al più $\frac12$
Spiegazione. Lo schema permette di scegliere la precisione: per ogni $\varepsilon$ c'è un algoritmo con errore relativo $\le\varepsilon$ su tutte le istanze.
Uno schema ha tempo $O(n^{1/\varepsilon})$. Di che cosa si tratta?
Un algoritmo esatto polinomiale
Un PTAS, ma non un FPTAS
Un FPTAS
Né un PTAS né un FPTAS
Spiegazione. Per $\varepsilon$ fisso il tempo è polinomiale in $n$ (PTAS), ma l'esponente cresce con $\frac1\varepsilon$: non è polinomiale in $\frac1\varepsilon$, quindi non è un FPTAS.
Che cosa si chiama «accuratezza» di uno schema di approssimazione?
L'errore relativo $\varepsilon$
Il rapporto $1+\varepsilon$
Il tempo di calcolo
La quantità $\frac1\varepsilon$
Spiegazione. Più piccolo è $\varepsilon$, più grande è $\frac1\varepsilon$ e più precisa è la soluzione: per questo $\frac1\varepsilon$ si chiama accuratezza.
Uno schema per un problema di massimo ha errore relativo $\varepsilon=\frac14$. Che garanzia di approssimazione dà?
$\varepsilon=\frac14$, cioè $\frac14$
$1-\varepsilon=\frac34$
$\frac{1}{1-\varepsilon}=\frac43$
$1+\varepsilon=\frac54$
Spiegazione. Per un problema di massimo $\mathscr{A}_\varepsilon(I)\ge(1-\varepsilon)z(I)$, quindi $z(I)/\mathscr{A}_\varepsilon(I)\le\frac{1}{1-\varepsilon}$; $1+\varepsilon$ vale per i problemi di minimo.
$\mathscr{A}_\varepsilon(I)=z(I)$ per $\varepsilon$ abbastanza piccolo
Spiegazione. Da $(\mathscr{A}_\varepsilon(I)-z(I))/z(I)\le\varepsilon$ segue $\mathscr{A}_\varepsilon(I)\le(1+\varepsilon)z(I)$: la garanzia è relativa, non additiva.
Che cosa significa $e(\mathscr{A})=\infty$ per un algoritmo $\mathscr{A}$?
$\mathscr{A}$ non ha alcuna garanzia relativa finita
$\mathscr{A}$ non termina
$\mathscr{A}$ restituisce soluzioni inammissibili
$\mathscr{A}$ non ha alcuna garanzia additiva finita
Spiegazione. $e(\mathscr{A})$ è la più piccola garanzia additiva: se è infinito, la differenza dall'ottimo non è limitata da nessuna costante. Una garanzia relativa può comunque esistere.
Quale relazione vale fra le classi di schemi di approssimazione?
PTAS e FPTAS sono la stessa cosa
Un FPTAS non è uno schema di approssimazione
Ogni FPTAS è un PTAS, non viceversa
Ogni PTAS è un FPTAS
Spiegazione. Un tempo polinomiale in $n$ e in $\frac1\varepsilon$ è in particolare polinomiale in $n$ per $\varepsilon$ fisso; $O(n^{1/\varepsilon})$ mostra che il contrario è falso.
Le garanzie di approssimazione del capitolo usano $\mathscr{A}(I)\ge z(I)$ (minimo) o $\mathscr{A}(I)\le z(I)$ (massimo). Quale ipotesi su $\mathscr{A}$ serve?
Che l'istanza abbia un'unica soluzione ottima
Che restituisca sempre una soluzione ammissibile
Che $\mathscr{A}$ sia un algoritmo polinomiale
Che $\mathscr{A}$ sia un algoritmo greedy
Spiegazione. Il confronto con l'ottimo vale perché la soluzione euristica è ammissibile: una soluzione inammissibile potrebbe valere più dell'ottimo.
Perché altrimenti il problema non ha soluzioni ammissibili
Perché gli algoritmi greedy richiedono pesi positivi
Per poter usare la garanzia additiva
Spiegazione. Con $z(I)=0$ i rapporti non sono definiti e con valori di segno diverso non hanno senso; la garanzia additiva invece non richiede la positività.
Un algoritmo ha $\mathscr{A}(I)\le 2z(I)$ su tutte le istanze tranne una famiglia infinita. È una $2$-approssimazione?
Sì, se la famiglia è infinita ma rara
Sì: basta che valga sulle istanze di riferimento
Sì, se $r(\mathscr{A})<\infty$ sulle altre istanze
No: deve valere per ogni istanza
Spiegazione. La definizione richiede la disuguaglianza per ogni istanza $I$: anche una sola istanza con rapporto maggiore di $2$ fa cadere la garanzia $2$.
Nella definizione di PTAS il tempo di $\mathscr{A}_\varepsilon$ deve essere polinomiale nella taglia dell'istanza: per quali $\varepsilon$?
Solo per $\varepsilon=\frac12$
Per nessun $\varepsilon$: basta che sia pseudo-polinomiale
Per ogni $\varepsilon\in(0,1)$ fissato
Uniformemente in $\varepsilon$, con lo stesso polinomio
Spiegazione. Per un PTAS basta che ogni $\mathscr{A}_\varepsilon$, con $\varepsilon$ fisso, sia polinomiale; se il tempo è polinomiale anche in $\frac1\varepsilon$ lo schema è un FPTAS.
Per dimostrare che una garanzia relativa $\alpha$ è tight, che cosa basta esibire?
Un'istanza con rapporto maggiore di $\alpha$
Un'istanza con rapporto esattamente $\alpha$
Un'istanza su cui l'algoritmo è ottimo
Una dimostrazione che $\mathscr{A}(I)\le\alpha z(I)$
Spiegazione. La disuguaglianza $\mathscr{A}(I)\le\alpha z(I)$ dimostra la garanzia; la tightness richiede istanze che la raggiungono o la avvicinano quanto si vuole. Un rapporto maggiore di $\alpha$ smentirebbe la garanzia.
Su tre istanze un algoritmo per un problema di minimo ha rapporti $1$, $\frac32$ e $\frac43$, e nessuna istanza fa peggio di $\frac32$. Quanto vale $r(\mathscr{A})$?
$1$
$\frac{23}{18}$
$\frac32$
$\frac43$
Spiegazione. $r(\mathscr{A})$ è l'estremo superiore dei rapporti su tutte le istanze, non la media: $\frac32$.
Per il problema dello zaino (KP): $GR$ è il greedy per efficienza, $GR^e$ prende il meglio fra $GR$ e il miglior oggetto singolo, $H^2$ prova tutti i sottoinsiemi di al più due oggetti completandoli con il greedy; $r(\cdot)$ è il rapporto nel caso peggiore. Quale affermazione è corretta?
$GR$, $GR^e$ e $H^2$ hanno tutti rapporto $2$
$GR$ non ha garanzia costante, $GR^e$ ha $r(GR^e)=2$, $H^2$ ha $r(H^2)=\frac43$
$GR$ ha $r(GR)=2$ e $GR^e$ ha $r(GR^e)=\frac43$
$GR^e$ ha $r(GR^e)=\frac32$ e $H^2$ ha $r(H^2)=2$
Spiegazione. Il greedy per efficienza può essere arbitrariamente cattivo; prendere il meglio fra $GR$ e il miglior oggetto singolo dà $2$; indovinare due oggetti ($H^2$) dà $\frac43$; tutti i rapporti sono tight.
Nel problema dello zaino, $GR$ è il greedy per efficienza, $p_{\max}$ il profitto massimo di un oggetto e $GR^e(I)=\max\{GR(I),p_{\max}\}$; con gli oggetti ordinati per efficienza, $s$ è l'oggetto critico. Quali fatti si usano per dimostrare $z(I)/GR^e(I)\le 2$?
$z(I)=GR(I)$ con gli oggetti ordinati; $GR(I)\ge p_s$; $p_{\max}\ge p_s$
Spiegazione. $z(I)\le z(\mathrm{LP}_{\mathrm{KP}})\le\sum_{i<s}p_i+p_s\le GR(I)+p_{\max}\le 2\,GR^e(I)$: il greedy prende almeno gli oggetti prima di $s$, e il miglior oggetto singolo vale almeno $p_s$.
Per il problema dello zaino (KP), l'algoritmo $H^{\ell}$ prova tutti i sottoinsiemi di al più $\ell$ oggetti e completa ciascuno con il greedy per efficienza. Quale rapporto di prestazione nel caso peggiore garantisce con $\ell=3$?
$\frac43$
$\frac32$
$\frac65$
$\frac54$
Spiegazione. $r(H^{\ell})=\frac{\ell+2}{\ell+1}$: con $\ell=3$ si ha $\frac54$. Il tempo $O(n^{\ell+1})$ cresce con $\ell$: la famiglia è un PTAS, non un FPTAS.
Per il problema dello zaino (KP, $n$ oggetti, capacità $c$, profitti interi), un algoritmo ha garanzia assoluta $k$ se $z(I)-\mathscr{A}(I)\le k$ per ogni istanza. Che cosa afferma il teorema sulla garanzia assoluta per il KP?
Esiste un algoritmo polinomiale con garanzia assoluta $p_{\max}$, il profitto massimo di un oggetto
Esiste un algoritmo polinomiale con garanzia assoluta $1$, ottenuto arrotondando il bound di Dantzig
Un algoritmo con garanzia assoluta $k$ e tempo $O(f(n,c))$ risolverebbe all'ottimo ogni istanza nello stesso tempo
Un algoritmo con garanzia assoluta $k$ e tempo $O(f(n,c))$ darebbe un FPTAS con tempo $O(f(n,c)/k)$
Spiegazione. Moltiplicando i profitti per $k+1$ un errore assoluto $\le k$ diventa un errore nullo: un algoritmo con garanzia assoluta fissata risolverebbe il KP esattamente nello stesso tempo.
Zaino 0-1 con capacità $c=9$ e oggetti già ordinati per efficienza $p_j/w_j$ non crescente: $p=(10,7,6,4)$, $w=(5,4,3,3)$. L'oggetto critico $s$ è il primo che non entra per intero, e $\mathit{rc}=c-\sum_{j<s}w_j$ è la capacità residua. Quanto valgono $s$ e $\mathit{rc}$?
$s=2$, $\mathit{rc}=0$
$s=3$, $\mathit{rc}=3$
$s=4$, $\mathit{rc}=0$
$s=3$, $\mathit{rc}=0$
Spiegazione. I primi due oggetti pesano $5+4=9\le c$; aggiungendo il terzo si arriva a $12>9$, quindi $s=3$ e $\mathit{rc}=9-9=0$. Il secondo oggetto è l'ultimo che entra, non l'oggetto critico.
Nello zaino 0-1 (pesi $w_j\le c$, oggetti ordinati per efficienza non crescente) l'oggetto critico è il primo che non entra per intero. Perché si assume $\sum_j w_j>c$?
Perché altrimenti l'oggetto critico sarebbe il primo
Perché altrimenti il greedy non termina
Altrimenti tutti gli oggetti entrano, non c'è oggetto critico e prenderli tutti è ottimo
Perché altrimenti il rilassamento lineare è illimitato
Spiegazione. Con $\sum_j w_j\le c$ l'istanza è banale: il greedy prende tutto ed è ottimo. L'ipotesi garantisce che l'oggetto critico esista.
Zaino 0-1 con capacità $c=8$ e oggetti ordinati per efficienza non crescente: $p=(12,9,5,2)$, $w=(4,3,2,1)$. Il greedy $GR$ esamina gli oggetti in quest'ordine e prende ogni oggetto che entra, anche dopo l'oggetto critico. Quanto vale $GR(I)$?
$28$
$23$
$21$
$24$
Spiegazione. Entrano gli oggetti $1$ e $2$ (peso $7$); il $3$ non entra (sarebbe $9$); il $4$ sì (peso $8$): $12+9+2=23$. Fermarsi all'oggetto critico darebbe $21$.
Zaino 0-1 con capacità $c=M$ grande e due oggetti: $(p_1,w_1)=(2,1)$ e $(p_2,w_2)=(M,M)$. Il greedy per efficienza $GR$ prende prima l'oggetto $1$. Quanto vale il rapporto $z(I)/GR(I)$?
$\frac M2$, che cresce senza limite con $M$
$2$, per ogni $M$
$1$: $GR$ è ottimo
$\frac{M+2}{2}$, ma limitato da $2$
Spiegazione. L'oggetto $1$ ha efficienza $2>1$; dopo di esso l'oggetto $2$ non entra, quindi $GR(I)=2$ mentre $z(I)=M$. Per questo $GR$ non ha garanzia costante, e $GR^e$ aggiunge il confronto con il miglior oggetto singolo.
L'algoritmo Ext-Greedy per lo zaino è $GR^e(I)=\max\{GR(I),\,p_{\max}\}$, dove $GR$ è il greedy per efficienza e $p_{\max}$ il profitto massimo di un oggetto (che entra da solo). Sull'istanza con $c=M$, oggetti $(2,1)$ e $(M,M)$, quanto vale $GR^e(I)$?
$2$, il valore di $GR$
$M+2$, la somma dei profitti
$\frac M2$
$M$, il valore ottimo
Spiegazione. $GR(I)=2$ e $p_{\max}=M$, quindi $GR^e(I)=M=z(I)$: il confronto con l'oggetto singolo ripara proprio il caso in cui $GR$ fallisce.
Per lo zaino 0-1, l'algoritmo Ext-Greedy $GR^e(I)=\max\{GR(I),p_{\max}\}$ ha rapporto $z(I)/GR^e(I)\le 2$ su ogni istanza. Quale istanza mostra che $2$ non si può migliorare?
Oggetti tutti uguali: $GR^e$ è sempre ottimo
Un solo oggetto: il rapporto è $1$
$c=2M$ e tre oggetti $(2,1)$, $(M,M)$, $(M,M)$: $GR^e$ vale circa $M$, l'ottimo $2M$
$c=M$ e due oggetti $(2,1)$, $(M,M)$: $GR^e$ è ottimo
Spiegazione. Il greedy prende $(2,1)$ e uno degli oggetti $(M,M)$, poi l'altro non entra: $GR=M+2$; $p_{\max}=M$; l'ottimo prende i due oggetti grandi, $2M$. Il rapporto $\frac{2M}{M+2}$ tende a $2$.
L'algoritmo $H^2$ per lo zaino prova ogni coppia ammissibile di oggetti $(i,k)$, $i<k$. Dopo aver inserito $i$ e $k$, su quali oggetti esegue $GR^e$ per completare la soluzione?
Sugli oggetti con profitto maggiore di $\max\{p_i,p_k\}$
Sugli altri oggetti con profitto al più $\min\{p_i,p_k\}$ e peso al più la capacità residua
Su tutti gli altri oggetti, qualunque sia il profitto
Solo sugli oggetti più efficienti di $i$ e $k$
Spiegazione. $H^2$ indovina i due oggetti di profitto massimo di una soluzione ottima: gli oggetti residui devono quindi avere profitto non maggiore. Il risultato è il massimo fra tutti i completamenti e $p_{\max}$.
L'algoritmo $H^2$ per lo zaino con $n$ oggetti prova $O(n^2)$ coppie di oggetti e per ognuna esegue $GR^e$ sugli oggetti residui. Quanto tempo richiede?
$O(n^3)$, e $O(n^2)$ con un'implementazione più accurata
$O(n\log n)$, come il greedy
$O(2^n)$, perché prova sottoinsiemi
$O(n^4)$, per ogni implementazione
Spiegazione. Con gli oggetti già ordinati per efficienza, ogni completamento costa $O(n)$ e le coppie sono $O(n^2)$; un'implementazione più attenta scende a $O(n^2)$. In cambio la garanzia scende da $2$ a $\frac43$.
L'algoritmo $H^{\ell}$ per lo zaino prova tutti gli insiemi di $\ell$ oggetti e li completa con il greedy; ha rapporto nel caso peggiore $\frac{\ell+2}{\ell+1}$ e tempo $O(n^{\ell+1})$. Quanto valgono garanzia e tempo con $\ell=4$?
$\frac54$ e $O(n^4)$
$\frac65$ e $O(n^4)$
$\frac43$ e $O(n^5)$
$\frac65$ e $O(n^5)$
Spiegazione. $\frac{4+2}{4+1}=\frac65$ e $n^{4+1}=n^5$. Ogni oggetto in più nella «guess» migliora la garanzia e moltiplica il tempo per $n$.
Per lo zaino, $H^{\varepsilon}$ è $H^{\ell}$ con $\ell=\lceil 1/\varepsilon\rceil-2$ (almeno $2$ e al più $n$), e $H^{\ell}$ ha rapporto $\frac{\ell+2}{\ell+1}$. Con $\varepsilon=\frac1{10}$, quale $\ell$ si usa e quale rapporto si garantisce?
$\ell=8$ e rapporto $\frac98$
$\ell=9$ e rapporto $\frac{11}{10}$
$\ell=8$ e rapporto $\frac{10}{9}$
$\ell=10$ e rapporto $\frac{12}{11}$
Spiegazione. $\ell=10-2=8$ e $\frac{8+2}{8+1}=\frac{10}{9}$, cioè errore relativo al più $\frac1{10}$. Il tempo $O(n^{\ell+1})$ è polinomiale per $\varepsilon$ fissato: la famiglia è un PTAS.
Il Basic-FPTAS $FP^{\varepsilon}$ per lo zaino garantisce $z(I)/FP^{\varepsilon}(I)\le\frac1{1-\varepsilon}$. Con $\varepsilon=0{,}2$, quale garanzia si ottiene, e quale errore relativo?
Rapporto al più $5$, errore relativo al più $80\%$
Rapporto al più $\frac54$, errore relativo al più $20\%$
Rapporto al più $\frac65$, errore relativo al più $20\%$
Rapporto al più $\frac54$, errore relativo al più $25\%$
Spiegazione. $\frac1{1-0{,}2}=\frac54$; in termini di errore $\frac{z-FP}{z}\le\varepsilon=20\%$. $\frac65=1+\varepsilon$ sarebbe la garanzia di un problema di minimo.
Il Basic-FPTAS per lo zaino sostituisce i profitti $p_j$ con profitti scalati $\lfloor p_j/K\rfloor$ e risolve l'istanza scalata all'ottimo con la programmazione dinamica sui profitti. Perché il tempo diventa polinomiale in $n$ e in $\frac1\varepsilon$?
I profitti scalati sono piccoli (dell'ordine di $n/\varepsilon$), e la PD sui profitti costa in proporzione al profitto totale
Perché la PD sulla capacità non dipende dai profitti
Perché l'istanza scalata ha meno oggetti
Perché arrotondare i profitti rende ottimo il greedy
Spiegazione. Con $K$ proporzionale a $\varepsilon$ e a un bound sull'ottimo diviso per $n$, i profitti scalati sono limitati da un polinomio in $n$ e $\frac1\varepsilon$; la PD sui profitti richiede allora $O(n^2/\varepsilon)$ passi.
Il teorema sulla garanzia assoluta per lo zaino (profitti interi) afferma che un algoritmo con $z(I)-\mathscr{A}(I)\le k$ su ogni istanza risolverebbe all'ottimo ogni istanza nello stesso tempo. Quale costruzione si usa nella dimostrazione?
Dividere tutti i profitti per $k$ e arrotondare per difetto
Aggiungere $k$ oggetti fittizi di profitto nullo
Ridurre la capacità di $k$ unità
Moltiplicare tutti i profitti per $k+1$: due valori diversi distano almeno $k+1$, quindi un errore al più $k$ è nullo
Spiegazione. Sull'istanza $I'$ con profitti $(k+1)p_j$ le soluzioni sono le stesse, $z(I')=(k+1)z(I)$, e i valori sono multipli di $k+1$: l'errore al più $k$ deve essere $0$, e la soluzione è ottima anche per $I$.
Nel capitolo sull'approssimazione dello zaino 0/1, $z(I)$ è il valore ottimo e $\mathscr{A}(I)$ il profitto della soluzione di un'euristica $\mathscr{A}$. Quali relazioni valgono per ogni istanza?
$\mathscr{A}(I)\ge z(I)$ e $\mathscr{A}(I)/z(I)\ge1$
$\mathscr{A}(I)=z(I)$
$\mathscr{A}(I)\le z(I)$ e $\mathscr{A}(I)/z(I)\ge1$
$\mathscr{A}(I)\le z(I)$ e $z(I)/\mathscr{A}(I)\ge1$
Spiegazione. Lo zaino è un problema di massimo: la soluzione euristica vale al più l'ottimo, e il rapporto si scrive con l'ottimo al numeratore per essere almeno $1$.
L'algoritmo $H^2$ per lo zaino 0/1 considera ogni coppia ordinata ammissibile di oggetti $(i,k)$: la inserisce, poi riempie la capacità residua con un greedy sugli oggetti di profitto al più $\min\{p_i,p_k\}$. Su quale idea si basa?
Basta provare le coppie di oggetti più leggeri
La coppia migliore è sempre quella di profitto totale massimo
Una soluzione ottima o ha un solo oggetto, o contiene due oggetti di profitto massimo fra i suoi, che $H^2$ indovina provando tutte le coppie
Una soluzione ottima contiene sempre i due oggetti più efficienti
Spiegazione. Provando tutte le coppie, una di esse è formata dai due oggetti più redditizi di una soluzione ottima; gli altri oggetti ottimi hanno profitto al più il minimo della coppia e restano candidati del greedy.
Il greedy $GR$ per lo zaino 0/1 inserisce gli oggetti per efficienza non crescente, finché entrano. Sull'istanza con $c=\vartheta$, oggetto $1$ con $(p_1,w_1)=(2,1)$ e oggetto $2$ con $(p_2,w_2)=(\vartheta,\vartheta)$, quanto vale $z(I)/GR(I)$?
$(\vartheta+2)/\vartheta$
$\vartheta/2$, che cresce senza limite: $GR$ non ha garanzia costante
$2$, per ogni $\vartheta$
$1$: $GR$ è ottimo
Spiegazione. $GR$ prende l'oggetto $1$ (efficienza $2$) e poi l'oggetto $2$ non entra: $GR=2$, mentre $z=\vartheta$. Ext-Greedy, che confronta anche con il miglior oggetto singolo, risolve il problema.
Ext-Greedy per lo zaino 0/1 è $GR^e(I)=\max\{GR(I),\max_jp_j\}$ e garantisce $z(I)\le2\,GR^e(I)$. Sull'istanza con $c=2\vartheta$ e oggetti $(2,1)$, $(\vartheta,\vartheta)$, $(\vartheta,\vartheta)$, quanto vale $z(I)/GR^e(I)$?
$1$
$\frac{\vartheta}{2}$
$\frac32$
$\frac{2\vartheta}{\vartheta+2}$, che tende a $2$: la garanzia è stretta
Spiegazione. $GR$ prende $(2,1)$ e un $(\vartheta,\vartheta)$, poi l'altro non entra: $GR=\vartheta+2=GR^e$. L'ottimo prende i due oggetti grandi: $2\vartheta$.
L'algoritmo $H^2$ per lo zaino 0/1 garantisce $z(I)\le\frac43H^2(I)$. Sull'istanza con $c=4M$, oggetto $(2,1)$ e quattro oggetti $(M,M)$, $H^2$ vale $3M+2$. Perché il rapporto $\frac{4M}{3M+2}$ mostra che $\frac43$ non si può migliorare?
È minore di $1$
Tende a $2$
Tende a $\frac43$ per $M\to\infty$
Vale esattamente $\frac43$ per ogni $M$
Spiegazione. Una coppia di oggetti grandi lascia capacità $2M$; il greedy prende prima $(2,1)$, più efficiente, poi un solo $(M,M)$: $2M+2+M$. L'ottimo vale $4M$.
Istanza dello zaino 0/1 con $c=4M$, un oggetto $(p,w)=(2,1)$ e quattro oggetti $(M,M)$, con $M=10$. Quanto valgono il valore ottimo e il valore di $H^2$ (coppia di oggetti, poi greedy per efficienza sugli oggetti di profitto al più il minimo della coppia)?
$z=40$, $H^2=22$
$z=40$, $H^2=32$
$z=40$, $H^2=40$
$z=42$, $H^2=32$
Spiegazione. L'ottimo riempie lo zaino con i quattro oggetti grandi. La coppia migliore per $H^2$ è di due oggetti grandi: poi $(2,1)$ e un solo altro $(10,10)$ entrano ($1+10\le20$): $20+2+10=32$.
L'algoritmo $H^{\ell}$ per lo zaino 0/1 prova tutti gli insiemi di al più $\ell$ oggetti e completa ciascuno con il greedy; la sua garanzia è $\frac{\ell+2}{\ell+1}$, stretta. Quanto vale per $\ell=2$ e per $\ell=4$?
$\frac43$ e $\frac65$
$\frac32$ e $\frac54$
$2$ e $\frac43$
$\frac43$ e $\frac43$
Spiegazione. $\frac{2+2}{2+1}=\frac43$ (è $H^2$) e $\frac{6}{5}$. Più grande è $\ell$, migliore la garanzia, ma il tempo $O(n^{\ell+1})$ cresce.
La famiglia $H^{\varepsilon}$, cioè $H^{\ell}$ con $\ell(\varepsilon)=\lceil\frac1\varepsilon\rceil-2$, ha tempo $O(n^{\ell(\varepsilon)+1})$. Perché è un PTAS ma non un FPTAS per lo zaino 0/1?
Perché il tempo è esponenziale in $n$ per ogni $\varepsilon$
Perché non garantisce errore relativo $\varepsilon$
È anche un FPTAS
Per $\varepsilon$ fissato il tempo è polinomiale in $n$, ma l'esponente cresce con $\frac1\varepsilon$, quindi non è polinomiale in $\frac1\varepsilon$
Spiegazione. Un FPTAS chiede un tempo polinomiale sia in $n$ sia in $\frac1\varepsilon$; con $\varepsilon=\frac1{10}$, $H^{\varepsilon}$ richiede già $O(n^9)$.
Per $H^{\varepsilon}$ (lo zaino 0/1 con $\ell(\varepsilon)=\lceil\frac1\varepsilon\rceil-2$ e tempo $O(n^{\ell+1})$), quale esponente di $n$ serve per un errore relativo $\varepsilon=\frac15$?
$n^2$
$n^6$
$n^4$, perché $\ell=5-2=3$
$n^5$
Spiegazione. $\ell(\frac15)=\lceil5\rceil-2=3$ e il tempo è $O(n^{3+1})$. La crescita dell'esponente con la precisione è ciò che separa un PTAS da un FPTAS.
L'algoritmo Basic-FPTAS $FP^{\varepsilon}$ per lo zaino 0/1 scala i profitti con $p'_j=\lfloor p_j/K\rfloor$, $K=\varepsilon\,GR^e(I)/n$, e risolve all'ottimo l'istanza scalata. Quale garanzia ottiene?
$FP^{\varepsilon}(I)\ge z(I)-\varepsilon$
$FP^{\varepsilon}(I)\ge(1-\varepsilon)\,z(I)$
$FP^{\varepsilon}(I)=z(I)$
$FP^{\varepsilon}(I)\ge z(I)/2$
Spiegazione. Ogni profitto perde meno di $K$ nell'arrotondamento, quindi una soluzione perde meno di $nK=\varepsilon\,GR^e(I)\le\varepsilon\,z(I)$.
Il Basic-FPTAS per lo zaino 0/1 risolve l'istanza scalata con la PD sui profitti, troncando la tabella a $Q=\lfloor2n/\varepsilon\rfloor$ colonne, per un tempo $O(n^2/\varepsilon)$. Quale fatto giustifica il troncamento?
La garanzia $z(I)\le2\,GR^e(I)$ di Ext-Greedy limita il valore ottimo scalato a $2n/\varepsilon$
Il fatto che i profitti scalati siano al più $1$
Il fatto che $n\le Q$ sempre
Nessuno: il troncamento può perdere l'ottimo
Spiegazione. Il valore scalato ottimo è al più $z(I)/K=z(I)\,n/(\varepsilon\,GR^e(I))\le2n/\varepsilon$. Senza la garanzia di $GR^e$ la tabella dipenderebbe da $\sum_jp_j$.
Basic-FPTAS per lo zaino 0/1 con $n=10$ oggetti ed $\varepsilon=\frac1{10}$: la PD sui profitti scalati ha $n+1$ righe e al più $Q+1$ colonne, con $Q=\lfloor2n/\varepsilon\rfloor$. Quanto vale $Q$?
$20$
$100$
$2000$
$200$
Spiegazione. $Q=\lfloor2\cdot10\cdot10\rfloor=200$, quindi circa $11\cdot201$ celle: il tempo $O(n^2/\varepsilon)$ non dipende dai profitti originali.
Per lo zaino 0/1 il capitolo determina il rapporto di prestazione nel caso peggiore $z(I)/\mathscr{A}(I)$ di più algoritmi. Quale ordinamento delle garanzie è corretto?
Spiegazione. Ogni algoritmo migliora il precedente al prezzo di più tempo; con $\ell$ che cresce si ottiene un PTAS, e con lo scaling dei profitti un FPTAS.
Nello zaino 0/1 l'oggetto critico $s$ è il primo oggetto, nell'ordine per efficienza non crescente, che non entra per intero insieme ai precedenti. Perché esiste sempre, sotto l'ipotesi $\sum_jw_j>c$?
Perché ogni oggetto pesa più di $c/2$
Non esiste sempre: dipende dai profitti
In ordine, prima o poi il peso supera $c$
Perché l'oggetto meno efficiente pesa più di $c$
Spiegazione. Se tutti gli oggetti entrassero insieme si avrebbe $\sum_jw_j\le c$, contro l'ipotesi; il primo oggetto che fa superare $c$ è l'oggetto critico.
L'algoritmo greedy $GR$ per lo zaino scorre gli oggetti per efficienza non crescente e prende ogni oggetto che entra nella capacità residua. Con $c=9$ e oggetti ordinati $(p_j,w_j)=(8,4),(6,3),(5,5),(2,2)$, quanto vale $GR$?
$16$
$14$
$19$
$13$
Spiegazione. Prende $(8,4)$ e $(6,3)$ (peso $7$), salta $(5,5)$, prende $(2,2)$: $16$. $14$ si ferma all'oggetto critico.
Ext-Greedy per lo zaino restituisce la migliore fra la soluzione greedy $GR$ e il miglior oggetto singolo. Con $c=10$ e oggetti $(p_j,w_j)=(2,1)$ e $(10,10)$, quanto valgono $GR$ ed Ext-Greedy?
$GR=2$, Ext-Greedy $=12$
$GR=12$, Ext-Greedy $=12$
$GR=2$, Ext-Greedy $=10$
$GR=10$, Ext-Greedy $=10$
Spiegazione. $GR$ prende l'oggetto più efficiente $(2,1)$ e poi $(10,10)$ non entra; il miglior oggetto singolo vale $10$, che è l'ottimo.
L'algoritmo $H^2$ per lo zaino prova ogni coppia di oggetti $(i,k)$ come «i due oggetti di profitto maggiore di una soluzione ottima» e completa con Ext-Greedy sugli oggetti con $p_j\le\min\{p_i,p_k\}$ che entrano. Perché solo quegli oggetti?
Sono coerenti con la scommessa su $i$ e $k$
Perché gli altri oggetti sono sempre più pesanti
Per rendere ottima la soluzione greedy residua
Perché gli oggetti più profittevoli non entrano mai
Spiegazione. Se $i,k$ sono davvero i due più profittevoli dell'ottimo, gli altri oggetti dell'ottimo hanno profitto al più $\min\{p_i,p_k\}$: restringere l'istanza non perde quella soluzione.
L'algoritmo $H^{\ell}$ per lo zaino scommette sugli $\ell$ oggetti di profitto maggiore e completa ogni scommessa con Ext-Greedy in tempo $O(n)$; si calcola in $O(n^{\ell+1})$. Quanto tempo richiede con $\ell=3$?
$O(n^3)$
$O(3n)$
$O(2^n)$
$O(n^4)$
Spiegazione. Gli insiemi di $3$ oggetti sono $O(n^3)$, ognuno completato in $O(n)$: $O(n^4)$. Polinomiale per ogni $\ell$ fissato.
L'algoritmo $H^{\ell}$ per lo zaino esamina $O(n^{\ell})$ insiemi di $\ell$ oggetti, uno alla volta, completando ciascuno con Ext-Greedy. Quanta memoria richiede, oltre ai dati?
$O(nc)$
$O(2^n)$
$O(n)$
$O(n^{\ell})$
Spiegazione. Si tiene solo l'insieme corrente, la soluzione residua e il miglior valore: spazio $O(n)$. Le scommesse non vanno memorizzate tutte insieme.
Basic-FPTAS per lo zaino scala i profitti con $K=\varepsilon\,lb/n$ ($lb$ = valore di Ext-Greedy) e usa $p'_j=\lfloor p_j/K\rfloor$. Con $\varepsilon=0.1$, $lb=200$ e $n=10$, quanto valgono $K$ e il profitto scalato di un oggetto con $p_j=37$?
$K=0.5$, $p'_j=74$
$K=2$, $p'_j=18$
$K=2$, $p'_j=18.5$
$K=20$, $p'_j=1$
Spiegazione. $K=0.1\cdot200/10=2$ e $\lfloor37/2\rfloor=18$: i profitti scalati sono interi, per poter usare la PD sui profitti.
Basic-FPTAS per lo zaino risolve all'ottimo l'istanza con i profitti scalati $\lfloor p_j/K\rfloor$, lasciando invariati pesi e capacità, e restituisce quella soluzione. Perché è ammissibile per l'istanza originale?
Pesi e capacità non cambiano: i vincoli sono gli stessi
Perché i profitti scalati sono minori di quelli originali
Perché si scalano anche i pesi con lo stesso fattore
Non lo è sempre: va riparata con il greedy
Spiegazione. Lo scaling tocca solo l'obiettivo; le soluzioni ammissibili delle due istanze coincidono, e cambia solo il loro valore.
Per lo zaino (massimo) le garanzie sono scritte come $z(I)/\mathscr{A}(I)\le\alpha$. Un algoritmo con $\alpha=\frac43$ quale frazione dell'ottimo garantisce?
Almeno $\frac43$ di $z(I)$
Al più $\frac34$ di $z(I)$
Almeno $\frac13$ di $z(I)$
Almeno $\frac34$ di $z(I)$
Spiegazione. $z/\mathscr{A}\le\frac43$ equivale a $\mathscr{A}\ge\frac34z$. Un valore maggiore di $z$ è impossibile in un problema di massimo.
Zaino con $c$ grande e due oggetti: $(p,w)=(2,1)$ e $(c,c)$. Il greedy $GR$ (per efficienza, prende ciò che entra) che rapporto $z/GR$ ottiene, e che cosa mostra?
$c$: perché $GR$ vale solo $1$
$c/2$: il rapporto di $GR$ non è limitato
$2$: è proprio il caso peggiore di $GR$
$1$: qui $GR$ trova l'ottimo
Spiegazione. $GR$ prende $(2,1)$, più efficiente, e poi $(c,c)$ non entra: $GR=2$, $z=c$. Per $c\to\infty$ il rapporto cresce senza limite.
La famiglia $H^{\varepsilon}$ (cioè $H^{\ell}$ con $\ell(\varepsilon)=\lceil1/\varepsilon\rceil-2$) è un PTAS per lo zaino, con tempo $O(n^{\ell+1})$. Con $\varepsilon=0.1$, quanto valgono $\ell$ e l'esponente del tempo?
$\ell=8$, tempo $O(n^2/\varepsilon)$
$\ell=1$, tempo $O(n^2)$
$\ell=8$, tempo $O(n^9)$
$\ell=10$, tempo $O(n^{11})$
Spiegazione. $\lceil10\rceil-2=8$, quindi $O(n^9)$: polinomiale per $\varepsilon$ fissato, ma l'esponente cresce con $1/\varepsilon$; per questo non è un FPTAS.
Teorema: se un algoritmo polinomiale $\mathscr{A}$ per lo zaino avesse garanzia assoluta $k$ ($z-\mathscr{A}\le k$), risolverebbe il problema all'ottimo. Qual è l'idea della dimostrazione?
Aumentare la capacità di $k$
Moltiplicare i profitti per $k+1$
Dividere i profitti per $k$ e arrotondare
Togliere $k$ oggetti dall'istanza
Spiegazione. Sull'istanza con profitti $(k+1)p_j$ due valori diversi differiscono di almeno $k+1>k$: la soluzione di $\mathscr{A}$ è ottima, e lo è anche per l'istanza originale.
Lo zaino 0/1 è NP-difficile. Se $P\neq NP$, quale tipo di garanzia ammette in tempo polinomiale?
Solo relativa, fino a un FPTAS
Solo assoluta, con errore costante $k$
Entrambe, relativa e assoluta
Nessuna garanzia di alcun tipo
Spiegazione. Una garanzia assoluta costante darebbe l'ottimo in tempo polinomiale; le garanzie relative invece esistono (Ext-Greedy, $H^{\ell}$, FPTAS).
3. Algoritmi di approssimazione per il bin packing (42)
Nel bin packing (BPP), Next Fit (NF), Worst Fit (WF), First Fit (FF) e Best Fit (BF) sistemano gli oggetti uno alla volta nell'ordine dato. Quali sono i loro rapporti di prestazione nel caso peggiore $r(\cdot)$?
$r(NF)=r(WF)=2$ e $r(FF)=r(BF)=\frac{17}{10}$
$r(NF)=2$ e $r(WF)=r(FF)=r(BF)=\frac{17}{10}$
$r(NF)=r(WF)=r(FF)=r(BF)=2$
$r(NF)=\frac{17}{10}$ e $r(FF)=r(BF)=\frac32$
Spiegazione. Tutti gli algoritmi Any Fit hanno la proprietà half-full, quindi sono $2$-approssimazioni; WF raggiunge asintoticamente $2$ come NF, mentre FF e BF hanno $\frac{17}{10}$.
Nel bin packing (capacità $c$, pesi $w_i$, ottimo $z(I)$), una soluzione con $k$ contenitori ha la proprietà half-full se al più un contenitore ha peso totale al più $c/2$. Quali fatti servono per dimostrare che un algoritmo con questa proprietà è una $2$-approssimazione?
La proprietà dà $\sum_i w_i>(k-1)\frac c2$; il rilassamento lineare vale $\sum_i w_i/c$ e il suo duale ha soluzione intera
Ogni oggetto pesa più di $c/2$; ogni soluzione con $z(I)$ contenitori ha $\sum_i w_i\le z(I)\,c$; $k$ è intero
Gli oggetti sono ordinati per peso non crescente; $z(I)\ge\lceil\sum_i w_i/c\rceil$; $k$ è intero
La proprietà dà $\sum_i w_i>(k-1)\frac c2$; ogni soluzione con $z(I)$ contenitori ha $\sum_i w_i\le z(I)\,c$; $k$ è intero
Spiegazione. Dalle due disuguaglianze $(k-1)\frac c2<z(I)\,c$, cioè $k<2z(I)+1$, e per l'interezza $k\le 2z(I)$.
Nel bin packing, un algoritmo è Any Fit se apre un nuovo contenitore solo quando l'oggetto corrente non entra in nessuno di quelli già aperti. Quale fatto si usa per dimostrare che le sue soluzioni hanno la proprietà half-full (al più un contenitore con peso al più $c/2$)?
Gli oggetti sono ordinati per peso non crescente, quindi i primi contenitori sono pieni
Il numero di contenitori è al più $\frac{17}{10}z(I)$, quindi pochi contenitori sono vuoti
Il contenuto di due contenitori non sta mai in uno solo, qualunque sia la regola di scelta del contenitore
La regola sceglie sempre il contenitore con capacità residua minima, che si riempie per primo
Spiegazione. Se due contenitori avessero entrambi peso al più $c/2$ si potrebbero unire, ma la condizione Any Fit lo esclude. NF non è Any Fit, ma ha comunque garanzia $2$.
Nel bin packing, Next Fit (NF) tiene aperto un solo contenitore e, se l'oggetto non vi entra, lo chiude e ne apre uno nuovo. Un algoritmo è Any Fit se apre un nuovo contenitore solo quando l'oggetto non entra in nessuno dei precedenti. Perché NF non è Any Fit?
Può superare la capacità del contenitore aperto
Può aprire un contenitore per un oggetto che entrerebbe in un contenitore chiuso
Ordina gli oggetti per peso non crescente prima di sistemarli
Sceglie sempre il contenitore con capacità residua massima
Spiegazione. Un algoritmo Any Fit apre un nuovo contenitore solo se l'oggetto non entra in nessuno di quelli aperti finora; NF tiene aperto un solo contenitore.
Bin packing con capacità $c=10$ e oggetti di peso $6,5,4,3,2$ in quest'ordine. Next Fit (NF) tiene aperto un solo contenitore e ne apre uno nuovo quando l'oggetto non entra; First Fit (FF) mette ogni oggetto nel primo contenitore aperto in cui entra. Quanti contenitori usano?
NF $4$, FF $2$
NF $3$, FF $2$
NF $2$, FF $2$
NF $3$, FF $3$
Spiegazione. NF: $\{6\}$, $\{5,4\}$, $\{3,2\}$. FF: $\{6,4\}$, $\{5,3,2\}$: l'oggetto di peso $4$ torna nel primo contenitore, che NF ha già chiuso.
Nel bin packing con $n$ oggetti, Next Fit (NF) tiene aperto un solo contenitore alla volta. Quanto tempo richiede, e perché?
$O(n)$: ogni oggetto si confronta solo con il contenitore aperto
$O(n^2)$: ogni oggetto si confronta con tutti i contenitori
$O(n\log n)$: gli oggetti vanno ordinati
$O(2^n)$: si provano tutte le partizioni
Spiegazione. Un solo controllo per oggetto: se entra va nel contenitore aperto, altrimenti si apre un nuovo contenitore. La velocità si paga con contenitori poco pieni.
Bin packing con capacità $c=10$: tre contenitori aperti hanno capacità residue $2$, $5$ e $3$, e arriva un oggetto di peso $3$. Dove lo mettono First Fit (primo che lo contiene), Best Fit (residuo minimo fra quelli che lo contengono) e Worst Fit (residuo massimo)?
FF nel primo, BF nel primo, WF nel secondo
FF nel terzo, BF nel terzo, WF nel secondo
FF nel secondo, BF nel secondo, WF nel terzo
FF nel secondo, BF nel terzo, WF nel secondo
Spiegazione. Il primo contenitore (residuo $2$) non basta. FF prende il secondo, BF il residuo più piccolo sufficiente ($3$, il terzo), WF il più grande ($5$, il secondo). Tutti e tre sono algoritmi Any Fit.
Nel bin packing una soluzione ha la proprietà half-full se al più un contenitore ha peso totale al più $c/2$. Con $c=10$, una soluzione ha carichi $(4,4,7)$. Può essere stata prodotta da un algoritmo Any Fit (che apre un contenitore nuovo solo se l'oggetto non entra in nessuno dei precedenti)?
Sì, ma solo con Worst Fit
No, perché il carico totale $15$ non è multiplo di $c$
No: due contenitori hanno carico al più $5$, e il contenuto del secondo sarebbe entrato nel primo
Sì: ogni soluzione ammissibile si ottiene con qualche ordine degli oggetti
Spiegazione. Le soluzioni Any Fit hanno la proprietà half-full: quando si è aperto il secondo contenitore poco pieno, il suo primo oggetto entrava nell'altro. I carichi $4$ e $4$ violano la proprietà.
Next Fit (NF) non è un algoritmo Any Fit, eppure ha $NF(I)\le 2\,z(I)$ nel bin packing. Quale fatto si usa nella dimostrazione?
Il contenuto di due contenitori qualsiasi non sta in uno solo
Due contenitori consecutivi di NF hanno insieme peso maggiore di $c$
Ogni contenitore di NF ha peso maggiore di $c/2$
NF ordina gli oggetti per peso non crescente
Spiegazione. NF apre il contenitore $b+1$ solo perché il suo primo oggetto non entrava nel contenitore $b$: le coppie consecutive superano $c$, e sommando si ottiene la garanzia $2$.
Nel bin packing, una soluzione con $k$ contenitori e la proprietà half-full (al più un contenitore con peso al più $c/2$) soddisfa $\sum_j w_j>(k-1)\frac c2$. Con $\sum_j w_j=23$ e $c=10$, quanti contenitori può usare al più un algoritmo Any Fit?
$5$
$6$
$4$
$3$
Spiegazione. $23>(k-1)\cdot 5$ dà $k-1\le 4$, cioè $k\le 5$. Il bound sul peso dà $z(I)\ge\lceil 2{,}3\rceil=3$, coerente con la garanzia $k\le 2z(I)$.
First Fit, Best Fit e Worst Fit sono tutti algoritmi Any Fit per il bin packing, quindi hanno la proprietà half-full e rapporto al più $2$. Che cosa insegna il fatto che $r(WF)=2$ mentre $r(FF)=r(BF)=\frac{17}{10}$?
Worst Fit non è un algoritmo Any Fit
First Fit e Best Fit violano la proprietà half-full
Le garanzie dipendono solo dall'ordine degli oggetti
La condizione Any Fit da sola dà solo la garanzia $2$: la regola di scelta del contenitore conta
Spiegazione. La proprietà half-full vale per ogni regola Any Fit e dà $2$; per scendere a $\frac{17}{10}$ serve sapere quale contenitore si sceglie, primo o più pieno.
Next Fit (NF) per il bin packing ha rapporto nel caso peggiore $r(NF)=2$. Quale tipo di istanza lo avvicina?
Oggetti ordinati per peso non crescente
Oggetti tutti di peso $1$, con $c$ grande
Oggetti che alternano peso circa $c/2$ e peso molto piccolo: NF chiude ogni contenitore mezzo vuoto
Oggetti tutti di peso $c$: ogni algoritmo usa un contenitore per oggetto
Spiegazione. Con pesi $\frac c2,\epsilon,\frac c2,\epsilon,\dots$ NF mette in ogni contenitore un oggetto grande e uno piccolo, mentre l'ottimo accoppia i grandi e raccoglie i piccoli in pochi contenitori.
Nel capitolo sull'approssimazione del bin packing una soluzione è una partizione degli oggetti in schemi di carico, $z(I)$ è il numero minimo di contenitori e $\mathscr{A}(I)$ quello usato da un'euristica. Quale rapporto di prestazione si usa e quanto vale almeno?
$\mathscr{A}(I)/z(I)\le1$
$\mathscr{A}(I)/z(I)\ge1$
$z(I)/\mathscr{A}(I)\ge1$
$\mathscr{A}(I)-z(I)\ge1$
Spiegazione. Il bin packing è di minimo: la soluzione euristica usa almeno $z(I)$ contenitori, e il rapporto ha l'euristica al numeratore.
Un algoritmo per il bin packing è Any Fit se apre un nuovo contenitore solo quando l'oggetto non entra in nessun contenitore aperto. Quale fra Next Fit, First Fit, Best Fit e Worst Fit NON è Any Fit, e perché?
Next Fit: chiude il contenitore appena un oggetto non vi entra, anche se l'oggetto entrerebbe in uno precedente
First Fit: sceglie il primo contenitore
Best Fit: sceglie il contenitore più pieno
Worst Fit: sceglie il contenitore più vuoto
Spiegazione. FF, BF e WF differiscono solo nella regola di scelta fra i contenitori in cui l'oggetto entra, che Any Fit lascia libera; NF tiene aperto un solo contenitore.
In una soluzione prodotta da un algoritmo Any Fit per il bin packing, due contenitori qualsiasi hanno insieme peso maggiore di $c$. Perché?
Perché ogni contenitore è pieno oltre metà per costruzione della regola di scelta
Perché gli oggetti sono ordinati per peso
Non è vero per Worst Fit
Il primo oggetto del contenitore aperto dopo non entrava nell'altro, il cui carico non è mai diminuito
Spiegazione. Si usa solo la condizione Any Fit, non la regola di scelta: per questo la proprietà, e la garanzia $\mathscr{A}(I)\le2z(I)$, vale anche per WF.
Bin packing con $c=10$: i contenitori aperti hanno carichi $(5,8,3)$ e arriva un oggetto di peso $2$. In quale contenitore lo mette Best Fit (capacità residua minima fra quelli in cui entra)?
In un contenitore nuovo
Nel contenitore $2$, che diventa pieno
Nel contenitore $1$, il primo in cui entra
Nel contenitore $3$, il più vuoto
Spiegazione. Residue $5,2,7$: l'oggetto entra in tutti, e la residua minima è $2$, nel contenitore $2$. First Fit lo metterebbe nel $1$, Worst Fit nel $3$.
Worst Fit per il bin packing mette ogni oggetto nel contenitore aperto con capacità residua massima fra quelli in cui entra. Che garanzia ha nel caso peggiore, rispetto a First Fit?
Rapporto $2$, stretto; First Fit ha rapporto asintotico $\frac{17}{10}$
Rapporto $\frac{17}{10}$, come First Fit
Rapporto $\frac32$
Nessuna garanzia costante
Spiegazione. WF è Any Fit, quindi $WF(I)\le2z(I)$, e esistono istanze con $WF(I_n)/z(I_n)\to2$; FF e BF arrivano solo a $\frac{17}{10}$.
Per Worst Fit esistono istanze $I_n$ con $WF(I_n)/z(I_n)\to2$. Che cosa significa per la classe degli algoritmi Any Fit, che garantiscono $\mathscr{A}(I)\le2z(I)$?
Che nessun algoritmo Any Fit ha rapporto minore di $2$
Che Worst Fit non è Any Fit
Che First Fit ha rapporto $2$
Il bound $2$ non si può migliorare per la classe nel suo complesso; regole di scelta migliori possono migliorarlo per singoli algoritmi
Spiegazione. La condizione Any Fit da sola dà $2$; FF e BF, con regole di scelta migliori, scendono a $\frac{17}{10}$.
First Fit e Best Fit per il bin packing soddisfano $\mathscr{A}(I)\le\frac{17}{10}z(I)$ (Dósa e Sgall; la prima versione, del 1974, aveva un $+2$), e il fattore $\frac{17}{10}$ è stretto. Su un'istanza con $z(I)=100$, quanti contenitori può usare al più First Fit secondo questa garanzia?
$200$
$150$
$170$
$172$
Spiegazione. $\frac{17}{10}\cdot100=170$; $172$ è il bound più debole del 1974. Il bound $2z(I)=200$ della sola condizione Any Fit è più debole ancora.
La sola condizione Any Fit garantisce la proprietà del riempimento a metà e quindi $\mathscr{A}(I)\le2z(I)$. Che cosa succede alla garanzia se si toglie la condizione Any Fit, come fa Next Fit?
Next Fit ha garanzia $\frac{17}{10}$
Next Fit mantiene comunque $NF(I)\le2z(I)$, perché due contenitori consecutivi superano insieme $c$
Next Fit perde ogni garanzia costante
Next Fit diventa ottimo
Spiegazione. Per NF la proprietà vale solo per coppie di contenitori consecutivi, ma basta per la garanzia $2$; ciò che la condizione Any Fit aggiunge è la proprietà per ogni coppia.
Bin packing con capacità $c=10$. Next Fit (NF) esamina gli oggetti nell'ordine dato, tiene aperto un solo contenitore e, se l'oggetto non vi entra, lo chiude e ne apre uno nuovo. Con pesi, nell'ordine, $(4,7,2,5,6,3)$, quale vettore $bin$ ($bin_i$ = contenitore dell'oggetto $i$) restituisce NF?
$(1,2,2,3,4,5)$
$(1,2,2,3,4,4)$
$(1,2,1,3,4,1)$
$(1,2,2,3,3,4)$
Spiegazione. $4$ nel contenitore $1$; $7$ non entra (residuo $6$): contenitore $2$, poi $2$ (residuo $1$); $5$ apre il $3$; $6$ non entra (residuo $5$): contenitore $4$, dove entra anche $3$. $(1,2,1,3,4,1)$ è First Fit, che torna ai contenitori precedenti.
Nel bin packing ($c=10$), un algoritmo restituisce $bin=(1,1,2,3,3,3)$ ($bin_i$ = contenitore dell'oggetto $i$) con pesi $w=(5,4,8,3,3,2)$. Lo schema di carico $P_b$ è l'insieme degli oggetti con $bin_i=b$. Quanto valgono $P_3$ e il suo peso totale?
$P_3=\{4,5,6\}$, peso $8$
$P_3=\{3\}$, peso $8$
$P_3=\{3,4,5\}$, peso $14$
$P_3=\{6\}$, peso $2$
Spiegazione. $bin_4=bin_5=bin_6=3$, quindi $P_3=\{4,5,6\}$ con peso $3+3+2=8$. $\{3\}$ confonde l'indice del contenitore con quello dell'oggetto: l'oggetto $3$ sta nel contenitore $2$.
Nello pseudocodice di Next Fit per il bin packing, $rc$ è la capacità residua del contenitore aperto e si apre un nuovo contenitore se $w[i]>rc$. Che cosa fa NF quando arriva un oggetto con peso $w[i]$ esattamente uguale a $rc$?
Apre un nuovo contenitore e ve lo mette
Lo mette nel primo contenitore chiuso in cui entra
Lo scarta e passa all'oggetto successivo
Lo mette nel contenitore aperto, che resta con $rc=0$
Spiegazione. La condizione per aprire un contenitore è $w[i]>rc$, stretta: con $w[i]=rc$ l'oggetto entra e riempie esattamente il contenitore. NF non torna mai ai contenitori chiusi.
Si esegue First Fit (FF) su sei oggetti di peso $5,7,3,4,2,6$, esaminati in quest'ordine, con contenitori di capacità $10$: ogni oggetto va nel primo contenitore, in ordine di apertura, che può accoglierlo, altrimenti in uno nuovo. Qual è il risultato?
$4$, con carichi $(5,10,6,6)$
$4$, con carichi $(10,7,4,6)$
$3$, con carichi $(10,7,10)$
$3$, con carichi $(9,10,8)$
Spiegazione. $5\to1$, $7\to2$, $3\to1$ (residuo $5$), $4\to3$ (residui $2$ e $3$), $2\to1$, $6\to3$ (residuo $6$). $(9,10,8)$ è Best Fit, $(5,10,6,6)$ è Next Fit; $(10,7,4,6)$ dimentica di controllare il contenitore $3$ per l'oggetto $6$.
Nel bin packing un algoritmo Any Fit apre un nuovo contenitore solo se l'oggetto non entra in nessuno di quelli aperti, e lascia libera la scelta fra i contenitori in cui entra. Che cosa fissa First Fit?
Sempre l'ultimo contenitore aperto finora
Il primo contenitore (in ordine di apertura) in cui entra
L'ordine degli oggetti, esaminati per peso non crescente
Il contenitore con la capacità residua minima
Spiegazione. FF esamina gli oggetti nell'ordine dato e sceglie il primo contenitore adatto. Ordinare i pesi in modo non crescente è un'altra cosa (First Fit Decreasing); il residuo minimo è Best Fit; l'ultimo contenitore è l'idea di Next Fit.
Bin packing con $c=10$ e pesi, nell'ordine, $(5,7,3,3,4)$. Best Fit (BF) mette ogni oggetto, fra i contenitori aperti in cui entra, in quello con capacità residua minima (pareggi: il primo aperto), e apre un nuovo contenitore solo se non entra in nessuno. Quale vettore $bin$ ($bin_i$ = contenitore dell'oggetto $i$) restituisce?
$(1,2,2,1,3)$
$(1,2,1,2,3)$
$(1,2,2,3,3)$
$(1,2,1,3,3)$
Spiegazione. Il primo $3$ entra nei contenitori $1$ (residuo $5$) e $2$ (residuo $3$): BF sceglie il $2$, che si riempie. Il secondo $3$ va nel $1$ (residuo $2$), e $4$ apre il $3$. $(1,2,1,2,3)$ è First Fit (e qui anche Worst Fit), $(1,2,2,3,3)$ è Next Fit.
Bin packing con $c=10$: quattro contenitori aperti hanno capacità residue $(4,2,4,7)$ e arriva un oggetto di peso $3$. Best Fit sceglie, fra i contenitori in cui l'oggetto entra, quello con capacità residua minima, e a parità il primo aperto. Dove va l'oggetto?
Nel contenitore $2$
Nel contenitore $3$
Nel contenitore $4$
Nel contenitore $1$
Spiegazione. L'oggetto entra nei contenitori $1$, $3$, $4$ (residui $4,4,7$); il minimo $4$ è in parità fra $1$ e $3$, e vince il primo aperto. Il contenitore $2$ ha il residuo più piccolo ma l'oggetto non vi entra; il $4$ è la scelta di Worst Fit.
Bin packing con $c=10$ e pesi, nell'ordine, $(6,5,3,4,2)$. First Fit (FF) usa il primo contenitore in cui l'oggetto entra; Worst Fit (WF) quello con capacità residua massima fra quelli in cui entra; entrambi aprono un contenitore solo se l'oggetto non entra in nessuno. Quanti contenitori usano?
Entrambi $2$
Entrambi $3$
FF $3$, WF $2$
FF $2$, WF $3$
Spiegazione. Dopo $6$ e $5$ i residui sono $(4,5)$. FF mette $3$ nel primo ($\to(1,5)$), poi $4$ nel secondo ($\to(1,1)$) e apre un terzo per $2$. WF mette $3$ nel secondo ($\to(4,2)$), poi $4$ nel primo e $2$ nel secondo: $(10,10)$. Una garanzia peggiore ($r(WF)=2$) non impedisce di vincere su una singola istanza.
Nel bin packing, Worst Fit mette ogni oggetto, fra i contenitori aperti in cui entra, in quello con la capacità residua massima. Qual è l'idea di questa regola?
Esaminare per primi gli oggetti più pesanti
Non lasciare residui troppo piccoli per gli oggetti futuri
Riempire il più possibile ogni contenitore aperto
Chiudere ogni contenitore appena un oggetto non vi entra
Spiegazione. Mettendo l'oggetto nel contenitore più vuoto, WF distribuisce lo spazio libero ed evita residui inutilizzabili. Riempire il più possibile è l'idea opposta, di Best Fit; chiudere i contenitori è Next Fit; l'ordine per peso non fa parte di WF.
Bin packing con $c=10$ e pesi, nell'ordine, $(2,9,2,9,2,9)$. Next Fit tiene aperto un solo contenitore. Una soluzione ha la proprietà di riempimento a metà se al più un contenitore ha carico $\le c/2$. Quanti contenitori usa NF, e la sua soluzione ha la proprietà?
$6$, e non la ha: tre contenitori hanno carico $2$
$6$, e la ha: due contenitori consecutivi superano $10$
$4$, e la ha: un solo contenitore ha carico $\le5$
$3$, e la ha: ogni contenitore pesa $11$
Spiegazione. Nessun oggetto entra insieme al precedente ($2+9=11>10$), quindi NF apre $6$ contenitori, e tre hanno carico $2\le5$. Che due contenitori consecutivi superino $c$ è un'altra proprietà. $4$ contenitori sono quelli di First Fit, $(6,9,9,9)$.
Nel bin packing con capacità $c$, una soluzione ha la proprietà di riempimento a metà se al più un contenitore ha peso totale al più $c/2$. Quale condizione è equivalente?
Per ogni coppia di contenitori, insieme pesano più di $c$
Ogni contenitore, senza eccezioni, pesa più di $c/2$
Al più un contenitore non è riempito del tutto
Per ogni coppia di contenitori, almeno uno pesa più di $c/2$
Spiegazione. Se due contenitori pesassero entrambi al più $c/2$ la proprietà fallirebbe, e viceversa. «Insieme più di $c$» è la proprietà più forte delle soluzioni Any Fit; «ogni contenitore» non ammette l'eccezione.
Nel bin packing con $c=10$, una soluzione ha due contenitori con carichi $6$ e $1$. Ha la proprietà di riempimento a metà (al più un contenitore con carico $\le c/2$)? I due contenitori si possono fondere in uno?
No, non la ha; e sì, si possono fondere
No, non la ha; e non si possono fondere
Sì, la ha; e sì, si possono fondere
Sì, la ha; quindi non si possono fondere
Spiegazione. Solo il contenitore con carico $1$ è $\le5$: la proprietà vale; ma $6+1=7\le10$, quindi si fondono. La proprietà non impedisce la fusione: serve a dimostrare la garanzia $2$.
Nel bin packing, per una soluzione con $k$ contenitori e la proprietà di riempimento a metà si ottiene $(k-1)\frac c2<\sum_iw_i\le z(I)\,c$ ($z(I)$ = numero ottimo di contenitori). Come si conclude $k\le2z(I)$?
Da $\sum_iw_i\le c$, che vale per ogni istanza
Da $k-1<2z(I)$, perché $k$ e $z(I)$ sono interi
Da $k<2z(I)$, dividendo per $\frac c2$
Da $z(I)\ge2$, che vale per ogni istanza
Spiegazione. Dividendo per $\frac c2$ si ha $k-1<2z(I)$, cioè $k<2z(I)+1$; gli interi danno $k\le2z(I)$. Non si ottiene direttamente $k<2z(I)$.
Nel bin packing, la proposizione «se un algoritmo produce sempre soluzioni con la proprietà di riempimento a metà, allora $\mathscr{A}(I)\le2z(I)$» si applica a un algoritmo che NON è Any Fit ma produce sempre soluzioni con quella proprietà?
Sì: la dimostrazione usa solo la proprietà della soluzione
No: la dimostrazione usa la condizione Any Fit
Sì, ma solo nel limite $z(I)\to\infty$
No: serve anche ordinare gli oggetti per peso
Spiegazione. La dimostrazione conta i contenitori pieni oltre la metà e usa $\sum_iw_i\le z(I)c$: non guarda come è stata costruita la soluzione. La condizione Any Fit serve solo a garantire la proprietà.
Nel bin packing, l'istanza $I_n$ ha $c=n$ e $n$ oggetti (con $n$ multiplo di $4$) di peso alternato $\frac n2$ (indici dispari) e $2$ (indici pari). Next Fit usa $\frac n2$ contenitori e l'ottimo è $\frac n4+1$. Con $n=20$, quanto valgono $NF$, $z$ e il rapporto?
$NF=10$, $z=5$, rapporto $2$
$NF=20$, $z=6$, rapporto $\frac{10}3$
$NF=10$, $z=10$, rapporto $1$
$NF=10$, $z=6$, rapporto $\frac53$
Spiegazione. $NF=\frac{20}2=10$ e $z=\frac{20}4+1=6$: i $10$ oggetti grandi due a due e tutti i piccoli ($10\cdot2=20$) in un contenitore. $z=5$ dimentica il contenitore dei piccoli. Il rapporto tende a $2$ solo per $n\to\infty$.
Nel bin packing, due contenitori consecutivi di Next Fit pesano insieme più di $c$; sommando sulle coppie disgiunte si ricava $z(I)\ge\lfloor k/2\rfloor+1$, dove $k$ è il numero di contenitori di NF e $z(I)$ l'ottimo. Se NF usa $k=7$ contenitori, quanto vale almeno $z(I)$?
$7$
$2$
$4$
$3$
Spiegazione. $\lfloor7/2\rfloor+1=4$: le $3$ coppie pesano più di $3c$, quindi servono più di $3$ contenitori. $3$ dimentica il $+1$; infatti $k\le2z(I)-1=7$.
Nel bin packing, l'istanza $I_n$ ha $c=n$ e pesi alternati $\frac n2,2,\frac n2,2,\dots$; Worst Fit (contenitore con residuo massimo fra quelli in cui l'oggetto entra) vi usa $\frac n2$ contenitori. Perché WF non mette mai due oggetti di peso $\frac n2$ nello stesso contenitore?
Perché gli oggetti piccoli finiscono tutti nel primo contenitore aperto
Ogni oggetto piccolo va nel contenitore nuovo, che resta con residuo $\frac n2-2$
Perché due oggetti di peso $\frac n2$ insieme superano la capacità $c=n$
Perché Worst Fit non soddisfa la condizione Any Fit
Spiegazione. Il contenitore appena aperto ha il residuo massimo $\frac n2$, quindi riceve l'oggetto piccolo e scende a $\frac n2-2<\frac n2$. Due oggetti grandi starebbero insieme ($\frac n2+\frac n2=n$): è la regola WF a impedirlo.
Nel bin packing Next Fit e Worst Fit hanno lo stesso rapporto nel caso peggiore, $r(NF)=r(WF)=2$. Sono quindi equivalenti?
No: solo NF può lasciare molti contenitori pieni a metà o meno
Sì: lo stesso rapporto vuol dire le stesse soluzioni
No: WF usa sempre meno contenitori di NF, su ogni istanza
Sì: entrambi tengono aperto un solo contenitore alla volta
Spiegazione. WF è Any Fit, quindi ha la proprietà di riempimento a metà; NF può lasciare molti contenitori con carico $\le c/2$. Il rapporto nel caso peggiore guarda solo l'istanza peggiore; «sempre meno» è troppo forte.
Per First Fit e Best Fit nel bin packing, Johnson, Demers, Ullman, Garey e Graham (1974) dimostrarono $\mathscr{A}(I)\le\frac{17}{10}z(I)+2$; Dósa e Sgall (2013, 2014) dimostrarono $\mathscr{A}(I)\le\frac{17}{10}z(I)$. Che cosa cambia fra le due?
Il fattore è sceso da $2$ a $\frac{17}{10}$
Il risultato vale ora anche per Worst Fit
Il risultato vale ora solo con oggetti ordinati
È stata eliminata la costante additiva $+2$
Spiegazione. Il fattore $\frac{17}{10}$ c'era già nel 1974; il secondo risultato toglie il $+2$, quindi vale anche per $z(I)$ piccolo. Worst Fit ha $r(WF)=2$.
Nel bin packing un algoritmo Any Fit apre un nuovo contenitore solo se l'oggetto non entra in nessuno di quelli aperti. Si sa che nessun algoritmo Any Fit ha rapporto nel caso peggiore minore di $\frac{17}{10}$, e ogni Any Fit ha rapporto al più $2$. Un nuovo Any Fit sceglie il contenitore a caso: che cosa si sa del suo rapporto?
È al più $\frac{17}{10}$, come First Fit
Nulla: la condizione Any Fit non dà garanzie
È compreso fra $\frac{17}{10}$ e $2$
È esattamente $2$, come Worst Fit
Spiegazione. La condizione Any Fit dà la proprietà di riempimento a metà, quindi al più $2$; il lower bound $\frac{17}{10}$ di Johnson vale per tutta la classe. Gli estremi sono raggiunti da FF/BF e da WF.
Nel bin packing First Fit e Best Fit hanno rapporto nel caso peggiore $\frac{17}{10}$, Worst Fit $2$; tutti e tre esaminano gli oggetti nell'ordine dato e sono Any Fit (aprono un contenitore solo se l'oggetto non entra altrove). Che cosa spiega tutto il divario fra $\frac{17}{10}$ e $2$?
La costante additiva $+2$ del bound di First Fit
La regola con cui si sceglie fra i contenitori in cui l'oggetto entra
L'ordine in cui gli oggetti vengono esaminati
Il numero di contenitori tenuti aperti contemporaneamente
Spiegazione. I tre algoritmi hanno lo stesso ordine e tengono aperti tutti i contenitori; differiscono solo nella regola di scelta (primo, residuo minimo, residuo massimo).
4. Colorazione dei vertici: limiti dell'approssimazione (59)
Nella colorazione dei vertici (VCP) di un grafo $G$ con $n$ vertici si minimizza il numero di colori. Se $P\neq NP$, quale affermazione sull'approssimazione del VCP è corretta?
Ha una $(\Delta(G)+1)$-approssimazione per ogni grafo, $DSATUR$
Non ha $\alpha$-approssimazioni polinomiali per nessuna costante $\alpha\ge 1$
Ha una $\frac43$-approssimazione polinomiale, ma nessuna sotto $\frac43$
Ha una $2$-approssimazione polinomiale, la colorazione greedy
Spiegazione. Il teorema dei $\frac43$ esclude i rapporti sotto $\frac43$; il risultato di Zuckerman esclude anche $n^{1-\varepsilon}$, quindi nessuna costante. Il bound $GC(I)\le\Delta(G)+1$ non confronta con $\chi(G)$.
Nella colorazione dei vertici, sia $\chi(G)$ il numero cromatico. La dimostrazione che nessun algoritmo polinomiale $\mathscr{A}$ ha rapporto $\mathscr{A}(I)/\chi(G)$ minore di $\frac43$ su ogni grafo (se $P\neq NP$) usa:
che decidere se $\chi(G)\le 3$ è NP-completo, e che il numero di colori è intero
che decidere se $\chi(G)\le 2$ è NP-completo, e che il numero di colori è intero
che decidere se $\chi(G)\le 4$ è NP-completo, e che i grafi planari hanno $\chi(G)\le 4$
che la colorazione greedy usa al più $\Delta(G)+1$ colori, e che il numero di colori è intero
Spiegazione. Con rapporto $<\frac43$, un grafo con $\chi\le 3$ riceverebbe al più $3$ colori e uno con $\chi\ge 4$ almeno $4$: si deciderebbe la 3-colorabilità in tempo polinomiale. Con $2$ colori l'argomento non dice nulla, perché quel test è facile.
In un grafo di intervalli ogni vertice $v$ è un intervallo $[a_v,b_v]$ della retta, e due vertici sono adiacenti se gli intervalli si intersecano. Con quale ordine dei vertici la colorazione greedy (colore più piccolo libero) è ottima?
Per estremo destro $b_v$ non crescente
Per lunghezza $b_v-a_v$ non crescente
Con qualsiasi ordine dei vertici
Per estremo sinistro $a_v$ non decrescente
Spiegazione. Con gli intervalli ordinati per estremo sinistro, quando un intervallo riceve il colore $q$ ci sono $q$ intervalli che si intersecano in $a_v$: la colorazione usa $\omega(G)$ colori, quindi è ottima.
Un grafo $G$ con $n$ vertici e $m$ lati è bipartito se e solo se il suo numero cromatico è $\chi(G)\le 2$. Quanto costa decidere se $G$ è bipartito e, in caso affermativo, trovare una colorazione con $2$ colori?
$O(2^n)$: il problema è NP-completo
$O(nm)$, con un cammino minimo da ogni vertice
$O(n+m)$, con una visita in ampiezza
$O(n^3)$, con la programmazione lineare
Spiegazione. Una visita in ampiezza colora alternando due colori e trova un ciclo dispari se il grafo non è bipartito. Già con $3$ colori il problema è NP-completo.
La dimostrazione che nessun algoritmo polinomiale per la colorazione ha rapporto $\mathscr{A}(I)/\chi(G)<\frac43$ su ogni grafo (se $P\neq NP$) usa un algoritmo ipotetico con rapporto $<\frac43$. Che cosa farebbe su un grafo con $\chi(G)=3$?
Userebbe $2$ colori, contraddicendo $\chi(G)=3$
Non terminerebbe, perché il problema è NP-difficile
Userebbe meno di $4$ colori, cioè $3$: deciderebbe in tempo polinomiale se $\chi(G)\le 3$
Userebbe esattamente $4$ colori, il che non dice nulla
Spiegazione. Con rapporto $<\frac43$ e $\chi(G)=3$ il numero di colori è $<4$, quindi $3$; se $\chi(G)\ge 4$ è almeno $4$. Si deciderebbe la 3-colorabilità, NP-completa: si usa solo l'interezza di $\chi$.
Lo stesso argomento che esclude rapporti minori di $\frac43$ per la colorazione (distinguere $3$ colori da $4$) non esclude rapporti minori di $\frac32$ distinguendo $2$ colori da $3$. Perché?
Perché con $2$ colori la colorazione greedy è sempre ottima
Decidere se $\chi(G)\le 2$ è polinomiale (grafi bipartiti), quindi non si ottiene nessuna contraddizione
Perché nessun grafo ha $\chi(G)=2$
Perché $\frac32>\frac43$
Spiegazione. L'argomento richiede un problema di decisione NP-completo; la 2-colorabilità si decide con una visita in ampiezza in $O(n+m)$.
Per la colorazione dei vertici, dare a ogni vertice un colore diverso è sempre ammissibile. Quale rapporto garantisce questo algoritmo banale, e che cosa dice il teorema di Zuckerman (se $P\neq NP$)?
Rapporto al più $n$; nessun algoritmo polinomiale garantisce $n^{1-\varepsilon}$ per nessun $\varepsilon>0$
Rapporto al più $2$; nessun algoritmo polinomiale garantisce meno di $2$
Rapporto al più $\Delta+1$; nessun algoritmo polinomiale garantisce meno di $\frac43$
Rapporto al più $\log n$; esiste un algoritmo con rapporto costante
Spiegazione. $n$ colori contro $\chi(G)\ge 1$ danno rapporto al più $n$. Il teorema dice che non si può fare sostanzialmente meglio: in particolare il problema non ha rapporti costanti.
Ogni grafo planare con $n\ge 3$ vertici ha al più $3n-6$ lati e quindi un vertice di grado al più $5$. Quanti lati ha al più un grafo planare con $n=10$ vertici?
$30$
$45$
$27$
$24$
Spiegazione. $3\cdot 10-6=24$. La somma dei gradi è al più $48<6n$, quindi qualche vertice ha grado al più $5$: è il passo chiave del teorema dei cinque colori.
Sui grafi planari, l'algoritmo $PL$ colora con al più $5$ colori in tempo polinomiale (teorema di Heawood). Che garanzia ha rispetto al numero cromatico $\chi(G)$, se il grafo ha almeno un lato?
Nessuna: i grafi planari sono difficili come tutti gli altri
Additiva: $PL(I)-\chi(G)\le 0$, cioè $PL$ è esatto
Additiva: $PL(I)-\chi(G)\le 2$, riconoscendo a parte i grafi con $\chi(G)\le 2$
Relativa: $PL(I)/\chi(G)\le\frac43$
Spiegazione. Con almeno un lato $\chi(G)\ge 2$; i grafi bipartiti si riconoscono e colorano in $O(n+m)$, e sugli altri $\chi(G)\ge 3$, quindi $5-\chi(G)\le 2$. Con il teorema dei quattro colori l'errore scende a $1$.
La colorazione greedy usa al più $\Delta(G)+1$ colori, con $\Delta(G)$ grado massimo. Su grafi di grado massimo al più $3$ con almeno un lato, quale rapporto rispetto a $\chi(G)$ garantisce?
Esattamente $1$: su questi grafi è ottima
Al più $2$, perché usa al più $4$ colori e $\chi(G)\ge 2$
Al più $4$, perché usa al più $4$ colori e $\chi(G)\ge 1$
Al più $\frac43$, perché $\chi(G)\ge 3$
Spiegazione. $\frac{\Delta+1}{\chi(G)}\le\frac42=2$: sui grafi di grado limitato la colorazione greedy ha un rapporto costante, mentre sui grafi generali nessun algoritmo polinomiale ce l'ha.
Grafo di intervalli con vertici $[1,4]$, $[2,5]$, $[3,6]$, $[7,8]$ (due vertici adiacenti se gli intervalli si intersecano). La colorazione greedy con i vertici per estremo sinistro non decrescente usa $\omega(G)$ colori. Quanti colori servono?
$3$
$4$
$2$
$1$
Spiegazione. I primi tre intervalli si sovrappongono nel punto $3{,}5$ e formano una clique, quindi $\omega=3$; $[7,8]$ non interseca nessuno e riusa il colore $1$. Il greedy dà $3=\chi(G)$.
Il teorema di Zuckerman esclude, se $P\neq NP$, i rapporti $n^{1-\varepsilon}$ per la colorazione. Perché esclude anche ogni rapporto costante $\alpha$?
Perché ogni costante è minore di $\frac43$
Perché i rapporti costanti valgono solo sui grafi planari
Non lo esclude: esistono $\alpha$-approssimazioni con $\alpha$ grande
Sui grafi con $n$ abbastanza grande, $\alpha<n^{1-\varepsilon}$: una $\alpha$-approssimazione avrebbe rapporto sotto la soglia vietata
Spiegazione. Fissato $\varepsilon$, per $n>\alpha^{1/(1-\varepsilon)}$ si ha $\alpha<n^{1-\varepsilon}$; i grafi piccoli, in numero finito, si risolvono all'ottimo in tempo costante.
Nel capitolo sui limiti dell'approssimazione della colorazione, $\mathscr{A}(I)$ è il numero di colori di un algoritmo e $\chi(G)$ il numero cromatico. Quale rapporto si studia?
$\omega(G)/\mathscr{A}(I)$
$\mathscr{A}(I)/\chi(G)\ge1$
$\chi(G)/\mathscr{A}(I)\ge1$
$\mathscr{A}(I)-\chi(G)$, sempre $\le1$
Spiegazione. La colorazione è un problema di minimo: l'algoritmo usa almeno $\chi(G)$ colori, e il rapporto ha l'algoritmo al numeratore.
Il VCP non è approssimabile in generale, ma su alcune classi di grafi si risolve esattamente in tempo polinomiale. Quale fra queste è una di quelle classi, e con quale metodo?
I grafi completi: servono $2$ colori
I grafi con un triangolo: bastano $3$ colori
Tutti i grafi con $n\le100$
I grafi bipartiti: una visita in ampiezza trova una $2$-colorazione o un ciclo dispari
Spiegazione. Un grafo con almeno un lato è $2$-colorabile se e solo se non ha cicli dispari, e la visita lo decide in tempo lineare. I grafi completi richiedono $n$ colori.
La colorazione dei vertici (VCP, minimo numero di colori $\chi(G)$) non è approssimabile in generale. Su quali delle classi bipartiti, grado massimo limitato, planari, grafi di intervalli si risolve esattamente in tempo polinomiale, e su quali si ha solo una garanzia?
Esatta su grado limitato e intervalli; garanzia su bipartiti e planari
Esatta su bipartiti e intervalli; garanzia su grado limitato e planari
Esatta su tutte e quattro le classi
Esatta su bipartiti e planari; garanzia su intervalli e grado limitato
Spiegazione. Bipartiti: visita in ampiezza; intervalli: greedy per estremo sinistro, ottima. Grado limitato: $\Delta+1$ colori; planari: errore additivo al più $2$ (o $1$ con quattro colori). Decidere $\chi\le3$ resta NP-completo sui planari.
Se $P\neq NP$ nessun algoritmo polinomiale per la colorazione dei vertici ha rapporto $\mathscr{A}(I)/\chi(G)<\frac43$ su tutti i grafi. Perché questo non impedisce un algoritmo polinomiale esatto sui grafi bipartiti?
Il teorema parla di tutti i grafi; i difficili non sono bipartiti
Perché sui grafi bipartiti il numero cromatico è $\chi(G)=1$
Perché il teorema vale solo nell'ipotesi $P=NP$
Perché sui bipartiti la colorazione diventa un problema di massimo
Spiegazione. Un limite sul caso peggiore su tutti i grafi non vale su una classe ristretta: le riduzioni usano grafi con $\chi\ge3$. Un grafo bipartito con uno spigolo ha $\chi=2$.
Per decidere se $\chi(G)\le2$ si fa una visita in ampiezza dal vertice $1$ e si colora ogni vertice secondo la parità del suo livello $\ell(v)$. Grafo con spigoli $\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,5\},\{4,6\},\{5,6\}$: quale spigolo unisce due livelli di uguale parità, e che cosa certifica?
$\{4,6\}$: un cammino chiuso di lunghezza $6$, quindi $\chi\ge3$
Nessuno: il grafo è bipartito e $\chi=2$
$\{5,6\}$: un cammino chiuso di lunghezza $4$, quindi $\chi\ge3$
$\{4,5\}$: un cammino chiuso di lunghezza $5$, quindi $\chi\ge3$
Spiegazione. Livelli: $1\to0$; $2,3\to1$; $4,5\to2$; $6\to3$. Solo $\{4,5\}$ unisce due livelli pari: con i cammini dell'albero dà $\ell(4)+\ell(5)+1=5$, il ciclo $1,2,4,5,3$. Gli spigoli $\{4,6\}$ e $\{5,6\}$ uniscono livelli di parità diversa.
Un grafo $G$ è bipartito se $\chi(G)\le2$, cioè se i vertici si dividono in due insiemi stabili; per König questo accade se e solo se $G$ non ha cicli di lunghezza dispari. Quanto vale $\chi(G)$ per un grafo con almeno uno spigolo e senza cicli dispari?
Esattamente $3$
Dipende dal grado massimo $\Delta(G)$
Esattamente $2$
$1$ oppure $2$, secondo il grafo
Spiegazione. Senza cicli dispari $\chi\le2$; uno spigolo richiede due colori, quindi $\chi=2$. $\chi=1$ vale solo per i grafi senza spigoli.
La colorazione greedy $GC$ esamina i vertici in un ordine dato e dà a ciascuno il colore minimo non usato dai vicini già colorati; usa al più $\Delta(G)+1$ colori ($\Delta$ = grado massimo). Sulla stella con un centro e $9$ foglie, quanti colori usa $GC$ e quanto vale $\Delta+1$?
$2$ colori con ogni ordine; $\Delta+1=9$
$2$ colori con ogni ordine; $\Delta+1=10$
$10$ colori con ogni ordine; $\Delta+1=10$
Da $2$ a $10$ colori secondo l'ordine; $\Delta+1=10$
Spiegazione. Le foglie sono a due a due non adiacenti: prendono tutte lo stesso colore e il centro l'altro, in qualunque ordine. Il bound $\Delta+1$ non confronta $GC$ con $\chi$: qui è $10$ contro $\chi=2$.
La colorazione greedy usa al più $\Delta(G)+1$ colori su ogni grafo ($\Delta$ = grado massimo). Su quali grafi connessi il bound è raggiunto con qualunque ordine, e che cosa dice il teorema di Brooks sugli altri?
Grafi completi e cicli dispari; per gli altri $\chi(G)\le\Delta(G)$
Alberi e cicli pari; per gli altri $\chi(G)\le\Delta(G)-1$
Grafi planari; per gli altri $\chi(G)\le4$
Grafi bipartiti; per gli altri $\chi(G)=\Delta(G)+1$
Spiegazione. $K_n$ ha $\chi=n=\Delta+1$ e un ciclo dispari ha $\chi=3=\Delta+1$. Brooks (1941): un grafo connesso che non è né completo né un ciclo dispari ha $\chi\le\Delta$, e tale colorazione si trova in tempo lineare.
Sui grafi planari l'algoritmo dei quattro colori dà una colorazione con errore additivo $\mathscr{A}(I)-\chi(G)\le1$. Decidere se un grafo planare ha $\chi(G)\le3$ è NP-completo. Che cosa se ne conclude, se $P\neq NP$?
Sui planari esiste un algoritmo esatto, ma non polinomiale in $n$
L'errore additivo minimo possibile sui planari è $2$
Sui planari nessun algoritmo ha rapporto costante
L'errore $1$ non scende a $0$ e $\frac43$ è il miglior rapporto sui planari
Spiegazione. Un algoritmo esatto deciderebbe $\chi\le3$; e un rapporto $<\frac43$ distinguerebbe $3$ colori da $4$. Il teorema dei quattro colori dà comunque il rapporto $\frac43$.
Il teorema di Heawood (ogni grafo planare si colora con $5$ colori) si dimostra per induzione: si toglie un vertice $v$, si colora $G-v$ e si rimette $v$. Perché si sceglie $v$ di grado al più $5$?
Perché così il grafo $G-v$ diventa bipartito
Perché ogni grafo planare ha grado massimo al più $5$
I vicini usano al più $5$ colori; se tutti, uno scambio ne libera uno
Perché i vertici di grado al più $5$ formano un insieme stabile
Spiegazione. Esiste per il lemma $m\le3n-6$. Con al più $4$ colori fra i vicini il quinto è libero; con $5$, scambiando due colori in una componente (catena di Kempe) se ne libera uno. Il grado massimo di un planare può essere grande (una stella).
In un grafo di intervalli ogni vertice $v$ è un intervallo chiuso $[a_v,b_v]$ e due vertici sono adiacenti se gli intervalli si intersecano. La colorazione greedy (a ogni vertice il colore minimo non usato dai vicini già colorati) è ottima se esamina i vertici in quale ordine?
Per numero di intersezioni (grado) non crescente
Per estremo sinistro $a_v$ non decrescente
In qualunque ordine: sui grafi di intervalli è sempre ottima
Per lunghezza $b_v-a_v$ non crescente
Spiegazione. Con l'ordine per $a_v$, i vicini già colorati di $v$ contengono tutti il punto $a_v$: con $v$ formano una clique, quindi i colori sono al più $\omega(G)$. Con altri ordini la greedy può usare un colore in più.
Grafo di intervalli con $[1,4],[2,6],[3,5],[5,8],[7,10],[9,12]$ (vertici $1,\dots,6$, adiacenti se gli intervalli si intersecano). La colorazione greedy usa $3$ colori nell'ordine $1,2,3,4,5,6$ e $4$ colori nell'ordine $1,2,3,5,4,6$. Che cosa mostra l'esempio?
L'ottimalità è garantita solo con l'ordine per estremo sinistro
Il numero cromatico di questo grafo è $\chi(G)=4$
Il grafo dato non è un grafo di intervalli
La colorazione greedy non è mai ottima su questi grafi
Spiegazione. $\{1,2,3\}$ contiene il punto $3$, quindi $\omega=\chi=3$: l'ordine per estremo sinistro è ottimo, l'altro usa un colore in più (il vertice $4$ ha vicini $2,3,5$ con colori $1,2,3$).
Quale problema di decisione NP-completo si usa per dimostrare che nessun algoritmo polinomiale per il VCP ha rapporto sempre minore di $\frac43$ (se $P\neq NP$)?
Decidere se $\chi(G)\le3$
Decidere se $\chi(G)\le2$
Decidere se $G$ è planare
Decidere se $\omega(G)\le2$
Spiegazione. Con rapporto $<\frac43$, su un grafo con $\chi(G)=3$ l'algoritmo userebbe al più $3$ colori e su $\chi(G)\ge4$ almeno $4$: deciderebbe la $3$-colorabilità.
Il risultato di Zuckerman (2007) dice che, se $P\neq NP$, per ogni $\varepsilon>0$ nessun algoritmo polinomiale per il VCP ha sempre rapporto al più quale quantità?
$1+\varepsilon$
$\log n$
$\frac43-\varepsilon$
$n^{1-\varepsilon}$
Spiegazione. Il rapporto banale è $n$ (un colore per vertice); Zuckerman mostra che non si può fare molto meglio: neanche $n^{1-\varepsilon}$.
Con quale complessità si decide se $\chi(G)\le2$ (e si trova una $2$-colorazione se esiste)?
Non si sa in tempo polinomiale
$O(n+m)$, con una visita in ampiezza
$O(2^n)$, provando tutte le partizioni
$O(n^3)$, con un modello PLI
Spiegazione. La visita in ampiezza colora i livelli alternando i due colori; uno spigolo fra due vertici dello stesso colore prova che $G$ non è bipartito.
Che cosa afferma il teorema di Heawood (1890) sui grafi planari?
Ogni grafo planare è bipartito
Ogni grafo planare si colora con $5$ colori
Ogni grafo planare si colora con $3$ colori
Colorare un grafo planare con $5$ colori è NP-difficile
Spiegazione. Il vertice di grado al più $5$ permette una dimostrazione per induzione che diventa un algoritmo polinomiale; decidere la $3$-colorabilità resta difficile.
Su un grafo di intervalli, con quale ordine dei vertici la colorazione greedy è ottima?
Per grado decrescente dei vertici
Con qualunque ordine dei vertici
Per estremo sinistro $a_v$ non decrescente
Per estremo destro $b_v$ decrescente
Spiegazione. Con l'ordine per $a_v$, quando si colora $v$ tutti i suoi vicini colorati contengono il punto $a_v$: con $v$ formano una clique, quindi bastano $\omega(G)$ colori.
Quale conseguenza ha il risultato di Zuckerman per l'approssimazione del VCP (se $P\neq NP$)?
Nessuna $\alpha$-approssimazione costante
Il VCP ha un PTAS ma non un FPTAS
Il VCP ha una $\frac43$-approssimazione polinomiale
Il VCP ha un algoritmo polinomiale $2$-additivo
Spiegazione. Una costante $\alpha$ sarebbe minore di $n^{1-\varepsilon}$ per $n$ grande: niente rapporto costante, quindi niente schema di approssimazione.
Quale garanzia ha $PL$ sui grafi planari se l'algoritmo dei cinque colori si sostituisce con quello dei quattro colori?
Diventa esatto
Rapporto al più $\frac43$, non additivo
Errore additivo al più $1$
Errore additivo al più $2$
Spiegazione. Sui grafi non bipartiti $\chi(G)\ge3$ e si usano al più $4$ colori: errore $\le1$. Resta non esatto perché decidere $\chi(G)\le3$ è difficile.
Su un grafo di intervalli, quanto vale $\omega(G)$?
Il grado massimo del grafo più uno
Il numero di intervalli a due a due disgiunti
Il massimo di intervalli con un punto comune
Il numero totale degli intervalli
Spiegazione. Intervalli a due a due intersecanti hanno un punto in comune (proprietà di Helly sulla retta): le clique sono gli intervalli che contengono un punto.
Nel prodotto forte $G\boxtimes H$ i vertici sono le coppie $(u,x)$, e due coppie distinte sono adiacenti se ogni componente è uguale o adiacente nel proprio grafo. Con $\omega$ cardinalità di una clique massima, quale affermazione è corretta?
Spiegazione. Il prodotto di due clique è una clique del prodotto forte, e una clique del prodotto ha al più $|p(K)|\cdot\max_u|K_u|$ vertici: il numero di clique si moltiplica.
Nel problema della clique massima (MCP), con $\omega(G)$ cardinalità di una clique massima e $G\boxtimes G$ prodotto forte di $G$ con sé stesso, il teorema «una $\alpha$-approssimazione costante per l'MCP darebbe una $\beta$-approssimazione per ogni $\beta>1$» si dimostra usando:
$\omega(G\boxtimes G)=\omega(G)^2$; da una clique $K$ del prodotto si estrae una clique di $G$ con almeno $\sqrt{|K|}$ vertici; $\log n$ prodotti
$\omega(G)=\alpha(\overline{G})$; da un insieme stabile di $\overline{G}$ si estrae una clique di $G$; la proprietà half-full
$\omega(G\boxtimes G)=\omega(G)^2$; da una clique $K$ del prodotto si estrae una clique di $G$ con almeno $\sqrt{|K|}$ vertici; un numero costante di prodotti
$\omega(G\boxtimes G)=2\,\omega(G)$; da una clique $K$ del prodotto si estrae una clique di $G$ con almeno $|K|/2$ vertici; un numero costante di prodotti
Spiegazione. Applicare l'algoritmo a $G\boxtimes G$ dà rapporto $\sqrt\alpha$ su $G$; ripetendo un numero costante di volte il rapporto scende sotto ogni $\beta>1$. Un numero di prodotti che cresce con $n$ non sarebbe polinomiale.
Per i problemi della clique massima (MCP) e dell'insieme stabile massimo (MSSP) su un grafo $G$ con $n$ vertici, con $\omega(G)$ cardinalità di una clique massima, quale affermazione sui grafi planari è corretta?
$\omega(G)\le 5$ e l'MCP si risolve in $O(n^5)$, mentre l'MSSP resta NP-difficile
$\omega(G)\le 4$ e l'MCP si risolve in $O(n^4)$, mentre l'MSSP resta NP-difficile
$\omega(G)\le 4$ e l'MCP si risolve in $O(n^4)$; anche l'MSSP, passando al complementare
$\omega(G)\le 4$, ma l'MCP resta NP-difficile come l'MSSP
Spiegazione. Una clique di un grafo planare ha al più $4$ vertici, quindi basta enumerare i sottoinsiemi di al più $4$ vertici. Il complementare di un grafo planare non è planare: il caso facile non si trasferisce all'MSSP.
Un grafo ha $n=24$ vertici e grado massimo $\Delta(G)=5$. Un insieme stabile è massimale se non gli si può aggiungere nessun vertice. Quanti vertici ha almeno ogni insieme stabile massimale?
$4$
$5$
$6$
$20$
Spiegazione. Un insieme stabile massimale $S$ ha $|S|\ge\frac{n}{\Delta(G)+1}=\frac{24}{6}=4$: ogni vertice è in $S$ o adiacente a un vertice di $S$, e ogni vertice di $S$ copre al più $\Delta+1$ vertici.
Nel prodotto forte $G\boxtimes H$ i vertici sono le coppie $(u,x)$ con $u$ vertice di $G$ e $x$ di $H$. Quanti vertici ha $G\boxtimes G$ se $G$ ha $5$ vertici, e quanto vale la sua clique massima se $\omega(G)=2$?
$25$ vertici, $\omega(G\boxtimes G)=4$
$10$ vertici, $\omega(G\boxtimes G)=4$
$25$ vertici, $\omega(G\boxtimes G)=2$
$25$ vertici, $\omega(G\boxtimes G)=8$
Spiegazione. I vertici sono $5\cdot 5=25$, e $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$: $2\cdot 2=4$. Il prodotto si costruisce in tempo polinomiale.
Da una clique $K$ del prodotto forte $G\boxtimes G$ si ricava una clique di $G$: o la proiezione $p(K)$ (le prime componenti) o la fibra più grande (le seconde componenti con la stessa prima). Se $|K|=16$, quanti vertici ha almeno la clique di $G$ ricavata?
$8$
$16$
$2$
$4$
Spiegazione. $|K|\le|p(K)|\cdot\max_u|K_u|$, quindi il più grande dei due fattori è almeno $\sqrt{|K|}=4$. È il passo costruttivo dell'amplificazione.
Nel problema della clique massima, un algoritmo con rapporto $\omega(G)/\mathscr{A}(I)\le\alpha$ applicato a $G\boxtimes G$ dà una clique $K$ del prodotto, da cui si ricava una clique di $G$ con almeno $\sqrt{|K|}$ vertici. Che rapporto si ottiene su $G$ con $\alpha=4$?
$16$
$\frac43$
$2$
$4$
Spiegazione. $|K|\ge\omega(G)^2/\alpha$, quindi la clique ricavata ha almeno $\omega(G)/\sqrt\alpha$ vertici: rapporto $\sqrt 4=2$. Ripetendo i prodotti il rapporto scende sotto ogni costante maggiore di $1$.
Nel problema della clique massima, un solo vertice è sempre una clique. Quale rapporto $\omega(G)/\mathscr{A}(I)$ garantisce l'algoritmo che restituisce un vertice, e che cosa dice il teorema di Håstad e Zuckerman (se $P\neq NP$)?
Al più $\sqrt n$; esiste un PTAS
Al più $n$; nessun algoritmo polinomiale garantisce $n^{1-\varepsilon}$ per nessun $\varepsilon>0$
Al più $2$; nessun algoritmo polinomiale garantisce meno di $2$
Al più $\Delta+1$; esiste un algoritmo polinomiale con rapporto $\frac43$
Spiegazione. $\omega(G)\le n$, quindi un vertice dà rapporto al più $n$; il teorema dice che non si può fare sostanzialmente meglio, e in particolare esclude ogni rapporto costante.
Nel problema della clique massima su grafi di grado massimo $\Delta$, la clique massima si trova esattamente in $O(n\,2^{\Delta}\Delta^2)$ tempo, esaminando i sottoinsiemi dei vicini di ogni vertice. Quando questo tempo è polinomiale in $n$?
Per ogni $\Delta$ fissato, e anche quando $\Delta\le\log_2 n$
Solo per $\Delta\le 3$
Mai: $2^{\Delta}$ è sempre esponenziale
Solo sui grafi planari
Spiegazione. Con $\Delta\le\log_2 n$ si ha $2^{\Delta}\le n$, e il tempo è $O(n^2\log^2 n)$. Una clique contiene un vertice e alcuni suoi vicini, quindi basta esaminare i $2^{\Delta}$ sottoinsiemi del vicinato.
Per l'insieme stabile massimo su un grafo con grado massimo $\Delta(G)$, il greedy che aggiunge vertici finché è possibile trova un insieme stabile massimale $S$ con $|S|\ge\frac{n}{\Delta(G)+1}$. Che rapporto $\alpha(G)/|S|$ garantisce con $\Delta(G)=3$?
Al più $3$
Al più $\frac43$
Nessun rapporto costante
Al più $4$
Spiegazione. $\alpha(G)\le n$ e $|S|\ge\frac n4$ danno $\alpha(G)/|S|\le 4=\Delta+1$. Ogni vertice aggiunto esclude al più $\Delta$ vicini.
La clique massima su $G$ è l'insieme stabile massimo sul complementare $\overline G$, quindi i due problemi hanno gli stessi limiti di approssimazione sui grafi generali. Perché i casi particolari facili per la clique (grafi planari, grado limitato) non lo sono per l'insieme stabile?
Perché il complementare di un grafo planare è ancora planare
Perché sui grafi planari $\alpha(G)=\omega(G)$
Il complementare di un grafo planare o di grado limitato è denso: sulla classe originale l'insieme stabile resta NP-difficile
Perché l'insieme stabile massimo è sempre polinomiale
Spiegazione. Passare al complementare cambia la classe di grafi. Sui grafi planari l'insieme stabile massimo resta NP-difficile, ma è approssimabile (ha anche un PTAS).
Nel problema della clique massima su un grafo planare con $n$ vertici, perché basta esaminare i sottoinsiemi di al più $4$ vertici?
Perché i grafi planari hanno al più $4n$ lati
Ogni grafo planare ha $\omega(G)\le 4$ ($K_5$ non è planare): si controllano $O(n^4)$ sottoinsiemi
Perché ogni grafo planare ha grado massimo al più $4$
Perché ogni grafo planare è bipartito
Spiegazione. Una clique di $5$ vertici sarebbe un $K_5$, che non è planare; i sottoinsiemi di al più $4$ vertici sono $O(n^4)$ e si controllano in tempo costante ciascuno.
Nel capitolo sui limiti dell'approssimazione della clique massima, $\mathscr{A}(I)$ è il numero di vertici della clique restituita da un algoritmo e $\omega(G)$ il numero di clique. Quali relazioni valgono?
$\mathscr{A}(I)=\omega(G)$
$\mathscr{A}(I)\le\omega(G)$ e $\omega(G)/\mathscr{A}(I)\ge1$
$\mathscr{A}(I)\ge\omega(G)$
$\mathscr{A}(I)/\omega(G)\ge1$
Spiegazione. La clique massima è un problema di massimo: l'ottimo va al numeratore perché il rapporto sia almeno $1$.
Il grafo $G$ è il ciclo $1,2,\dots,7,1$ con la corda $\{1,3\}$, con $\omega(G)=3$. Il prodotto forte $G\boxtimes G$ ha $49$ vertici. Quanto vale $\omega(G\boxtimes G)$, e da quale clique è raggiunto?
$9$, da $\{1,2,3\}\times\{1,2,3\}$
$6$, da $\{1,2,3\}\times\{1,2\}$
$3$, da $\{1,2,3\}\times\{1\}$
$49$, da tutti i vertici
Spiegazione. Nel prodotto forte $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$: il prodotto di due clique è una clique. È lo strumento che amplifica un rapporto di approssimazione costante.
Nella clique massima, un algoritmo di $\alpha$-approssimazione ($\omega(G)/\mathscr{A}(I)\le\alpha$) applicato al prodotto forte $G\boxtimes G$ dà una $\sqrt\alpha$-approssimazione; ripetendo $t$ volte si ha il rapporto $\alpha^{1/2^t}$ su un grafo con $n^{2^t}$ vertici. Con $\alpha=16$, qual è il minimo $t$ per arrivare a rapporto $2$?
$t=2$, su un grafo con $2n^2$ vertici
$t=2$, su un grafo con $n^4$ vertici
$t=1$, su un grafo con $n^2$ vertici
$t=3$, su un grafo con $n^8$ vertici
Spiegazione. $16^{1/2}=4$, $16^{1/4}=2$: servono $2$ passi, e il grafo ha $n^{2^2}=n^4$ vertici. Con $t=1$ il rapporto è $4$; $t=3$ basta ma non è il minimo.
Per la clique massima ($\omega(G)$ = cardinalità massima di una clique, $n$ vertici), il teorema di Håstad (1999) e Zuckerman (2007) esclude il rapporto $\omega(G)/\mathscr{A}(I)\le n^{1-\varepsilon}$ per ogni $\varepsilon>0$. Che cosa distingue i due contributi?
L'ipotesi: $NP\neq ZPP$ per Håstad, $P\neq NP$ per Zuckerman
Il limite: $n^{1/2}$ per Håstad, $n^{1-\varepsilon}$ per Zuckerman
Il problema: clique per Håstad, insieme stabile per Zuckerman
La classe: grafi planari per Håstad, tutti i grafi per Zuckerman
Spiegazione. Il limite $n^{1-\varepsilon}$ è lo stesso; Håstad lo ottiene supponendo che i problemi NP non si risolvano in tempo polinomiale randomizzato, Zuckerman con la sola ipotesi $P\neq NP$.
Per la clique massima valgono, se $P\neq NP$: (i) nessun algoritmo polinomiale ha rapporto $\omega(G)/\mathscr{A}(I)\le n^{1-\varepsilon}$ (Håstad, Zuckerman); (ii) un rapporto costante darebbe ogni rapporto costante (prodotto forte). Che cosa si conclude?
Il problema ha un PTAS ma non un FPTAS
Il problema ha rapporto $2$ ma non un PTAS
Il problema ha rapporto $n^{1/2}$ ma non costante
Il problema non ha né un rapporto costante né un PTAS
Spiegazione. (i) esclude ogni costante (per $n>\alpha^2$ si avrebbe $\alpha<n^{1/2}$); un PTAS darebbe in particolare un rapporto costante. Anche $n^{1/2}=n^{1-1/2}$ è escluso da (i).
Ogni grafo planare con $n\ge3$ vertici ha al più $3n-6$ spigoli. Nella clique massima, perché questo implica che un grafo planare non contiene una clique di $5$ vertici?
$K_5$ ha $5$ vertici di grado $4$, più di $3$
$K_5$ ha più di $3\cdot5=15$ spigoli
$K_5$ ha $10$ spigoli, più di $3\cdot5-6=9$
$K_5$ non ha vertici di grado al più $5$
Spiegazione. Un sottografo di un planare è planare, e $K_5$ viola il bound: $10>9$. I suoi vertici hanno grado $4\le5$, e $10<15$.
Nella clique massima su un grafo con $n$ vertici e grado massimo $\Delta$, l'enumerazione dei sottoinsiemi di $N(v)$ per ogni vertice $v$ richiede tempo $O(n\,2^{\Delta}\Delta^2)$. Quando questo tempo è polinomiale in $n$?
Per ogni grafo con $\Delta\le\sqrt n$
Per $\Delta$ fissato, e anche per $\Delta\le\log_2n$
Solo per grafi con $\Delta\le3$, come i cubici
Mai: il fattore $2^{\Delta}$ resta esponenziale
Spiegazione. Con $\Delta\le\log_2n$ si ha $2^\Delta\le n$, e il tempo è $O(n^2\log^2n)$. Con $\Delta=\sqrt n$ il fattore $2^{\sqrt n}$ non è polinomiale.
Nella clique massima su grafi di grado limitato, per ogni vertice $v$ si esaminano tutti i $2^{\deg(v)}$ sottoinsiemi $S$ di $N(v)$ (vicini di $v$) e si tiene il più grande $\{v\}\cup S$ che sia una clique. Su un grafo con gradi $3,2,2,3,1,1$, quanti sottoinsiemi si esaminano in tutto?
$28$
$64$
$12$
$18$
Spiegazione. $2^3+2^2+2^2+2^3+2^1+2^1=8+4+4+8+2+2=28$. $64=2^6$ sono i sottoinsiemi di tutti i vertici, $12$ la somma dei gradi.
Nel prodotto forte $G\boxtimes G$, per una clique $K$ la proiezione $p(K)$ (prime componenti) e ogni fibra $K_u$ (seconde componenti con prima componente $u$) sono clique di $G$. Un algoritmo restituisce $K=\{1,2,3\}\times\{4,5\}$, con $|K|=6$. Quale clique di $G$ si ricava, e perché basta?
La fibra $\{4,5\}$: ha $2\ge\sqrt6$ vertici
$K$ stessa: è già una clique di $G$
$\{1,2,3,4,5\}$: unisce proiezione e fibra
$p(K)=\{1,2,3\}$: ha $3\ge\sqrt6$ vertici
Spiegazione. La più grande fra proiezione e fibre ha almeno $\sqrt{|K|}$ vertici, perché il prodotto delle due dimensioni è almeno $|K|$: qui $3\ge\sqrt6\approx2.45$, mentre $2<\sqrt6$. $K$ è fatta di coppie, non di vertici di $G$.
Nel prodotto forte $G\boxtimes H$, quando due vertici distinti $(u,x)$ e $(v,y)$ sono adiacenti?
Se $\{u,v\}\in E$ e anche $\{x,y\}\in F$, senza altri casi
Se $u=v$ oppure $x=y$, qualunque siano gli spigoli
Se $\{u,v\}\in E$ oppure $\{x,y\}\in F$, anche da soli
Se $u=v$ o $\{u,v\}\in E$, e $x=y$ o $\{x,y\}\in F$
Spiegazione. In ogni coordinata i due vertici devono coincidere o essere adiacenti; la seconda opzione è il prodotto tensoriale, che perde i lati «dritti».
La potenza forte $G^{\boxtimes k}$ di un grafo con $n$ vertici: quanti vertici ha e quanto vale il suo numero di clique?
$kn$ vertici e $k\,\omega(G)$
$n^k$ vertici e $k\,\omega(G)$
$kn$ vertici e $\omega(G)^k$
$n^k$ vertici e $\omega(G)^k$
Spiegazione. Applicando $k-1$ volte il prodotto forte: i vertici si moltiplicano e anche i numeri di clique. Per $k$ fisso la taglia resta polinomiale.
Un algoritmo con rapporto $\alpha=4$ per l'MCP, applicato a $G^{\boxtimes 2}$ e riportato su $G$, che rapporto garantisce su $G$?
$16$
$8$
$\sqrt4=2$
$4$
Spiegazione. Sul quadrato forte si trova una clique di taglia $\ge\omega(G)^2/4$, da cui una clique di $G$ di taglia $\ge\omega(G)/\sqrt4$: il rapporto diventa $\alpha^{1/k}$.
Il rapporto banale $n$ per l'MCP si ottiene restituendo che cosa?
Il vertice di grado minimo con i suoi vicini
Un solo vertice
Tutti i vertici
Un insieme stabile massimale
Spiegazione. Un vertice è sempre una clique e $\omega(G)\le n$: rapporto al più $n$. Håstad e Zuckerman mostrano che $n^{1-\varepsilon}$ non si raggiunge.
Perché i risultati negativi sull'MCP valgono anche per il problema dell'insieme stabile massimo (MSSP)?
Perché $\alpha(G)=\omega(\overline G)$, con lo stesso $n$
Perché ogni clique di $G$ è anche un insieme stabile di $G$
Perché l'MSSP è più facile dell'MCP su ogni grafo
Perché $\alpha(G)=\omega(G)$ vale per ogni grafo $G$
Spiegazione. $\alpha(G)=\omega(\overline G)$ e il complementare si costruisce in $O(n^2)$: un algoritmo per un problema dà lo stesso rapporto per l'altro.
Il bound $|S|\ge\frac{n}{\Delta(G)+1}$ vale per quale tipo di insieme stabile $S$?
Per ogni insieme stabile
Solo per un insieme stabile massimo
Solo per un insieme stabile trovato con la visita in ampiezza
Per ogni insieme stabile massimale
Spiegazione. La massimalità serve: ogni vertice fuori da $S$ ha un vicino in $S$. Un insieme stabile qualunque, per esempio vuoto, non rispetta il bound.
Per il TSP (giro più corto che visita tutte le città), $DT$ è l'algoritmo dell'albero doppio e $CH$ quello di Christofides; il TSP è metrico se vale la disuguaglianza triangolare. Se $P\neq NP$, quale affermazione è corretta?
Il TSP generale non ha approssimazioni costanti; sul TSP metrico $DT$ ha rapporto $2$ e $CH$ rapporto $\frac32$
Il TSP generale non ha approssimazioni costanti; sul TSP metrico $DT$ ha rapporto $\frac32$ e $CH$ rapporto $2$
Il TSP generale ha una $2$-approssimazione, $DT$; sul TSP metrico $CH$ ha rapporto $\frac32$
Il TSP generale non ha approssimazioni costanti; sul TSP metrico il nearest neighbour ha rapporto $\frac32$
Spiegazione. Una garanzia costante sul TSP generale deciderebbe il problema del ciclo hamiltoniano; con la disuguaglianza triangolare $DT$ e $CH$ hanno rapporti $2$ e $\frac32$, entrambi tight.
Nel TSP metrico, l'algoritmo dell'albero doppio $DT$ raddoppia un albero ricoprente minimo $T$ (di lunghezza $d(T)$), ne percorre un circuito euleriano e salta le città già visitate. Con $z(I)$ lunghezza del giro ottimo, quali fatti servono per dimostrare $DT(I)\le 2\,z(I)$?
$d(T)\le z(I)$; il matching perfetto minimo sulle città di grado dispari costa al più $z(I)/2$; le scorciatoie non allungano il cammino
$d(T)\le z(I)/2$; il circuito euleriano dell'albero raddoppiato è lungo $2d(T)$; le distanze sono simmetriche
Il giro del nearest neighbour è lungo al più $2z(I)$; ogni città ha grado pari; le distanze sono simmetriche
$d(T)\le z(I)$; il circuito euleriano dell'albero raddoppiato è lungo $2d(T)$; le scorciatoie non allungano il cammino
Spiegazione. Togliendo un lato dal giro ottimo si ottiene un albero ricoprente, quindi $d(T)\le z(I)$; le scorciatoie usano la disuguaglianza triangolare. Il matching serve a $CH$.
Nel TSP metrico, l'algoritmo di Christofides $CH$ aggiunge a un albero ricoprente minimo $T$ un matching perfetto minimo $M$ sulle città di grado dispari in $T$, percorre un circuito euleriano di $T\cup M$ e salta le città già visitate. Quali fatti servono per dimostrare $CH(I)\le\frac32\,z(I)$?
$d(T)\le z(I)$; $d(M)\le d(T)$; le città di grado dispari di $T$ sono in numero dispari
$d(T)\le z(I)$; il circuito dell'albero raddoppiato è lungo $2d(T)$; le distanze sono simmetriche
$d(T)\le z(I)$; $d(M)\le z(I)/2$; le scorciatoie non allungano il circuito euleriano di $T\cup M$
$d(T)\le z(I)/2$; $d(M)\le z(I)$; le scorciatoie non allungano il circuito euleriano di $T\cup M$
Spiegazione. Il circuito euleriano di $T\cup M$ è lungo $d(T)+d(M)\le z(I)+\frac{z(I)}2$; le città di grado dispari di un albero sono in numero pari, quindi il matching perfetto esiste.
La dimostrazione che il TSP generale non ha $\alpha$-approssimazioni polinomiali (se $P\neq NP$) parte da un grafo $G$ in cui si chiede se esiste un ciclo hamiltoniano. Quale istanza del TSP si costruisce?
Distanza $2$ sui lati e $1$ sulle coppie non adiacenti
Distanza $1$ sui lati di $G$ e $\alpha n+1$ sulle coppie non adiacenti: un'$\alpha$-approssimazione distinguerebbe i giri di lunghezza $n$ dagli altri
Distanza $1$ su tutte le coppie: ogni giro è ottimo
Distanze euclidee fra i vertici di $G$ disegnato nel piano
Spiegazione. Se $G$ è hamiltoniano l'ottimo vale $n$ e l'algoritmo restituisce al più $\alpha n$, quindi solo lati di $G$; altrimenti ogni giro usa una coppia non adiacente e supera $\alpha n$. Si deciderebbe un problema NP-completo.
Un'istanza del TSP è metrica se $d_{ij}\le d_{ik}+d_{kj}$ per tutte le terne. Quale delle seguenti famiglie di istanze è sempre metrica?
Le città nel piano con le distanze euclidee
Le istanze con distanze intere qualsiasi
Le istanze con $d_{ij}\in\{1,2\}$ e $d_{ij}\ne d_{ji}$
Le istanze con distanze generate a caso in $[1,100]$
Spiegazione. La distanza euclidea soddisfa la disuguaglianza triangolare. Le distanze $1$ e $2$ simmetriche sono metriche, ma qui sono asimmetriche; distanze casuali possono violarla.
Il TSP generale non ha approssimazioni costanti (se $P\neq NP$), il TSP metrico sì. Che cosa si sa della complessità del TSP metrico?
È polinomiale, perché la disuguaglianza triangolare permette le scorciatoie
È polinomiale sulle istanze euclidee, NP-difficile sulle altre
Non ammette nemmeno lui approssimazioni costanti
Resta NP-difficile, ma ammette algoritmi con rapporto costante come $2$ o $\frac32$
Spiegazione. La metrica non rende il problema facile, ma permette di trasformare cammini chiusi in giri senza allungarli: è la base dell'albero doppio e di Christofides.
Nel TSP metrico, l'algoritmo dell'albero doppio $DT$ calcola un albero ricoprente minimo $T$, ne raddoppia i lati, segue un circuito euleriano e salta le città già visitate. Se $d(T)=7$, che cosa si sa del giro di $DT$ e del giro ottimo $z(I)$?
$DT(I)\le 7$ e $z(I)\ge 14$
$DT(I)\le\frac{21}{2}$ e $z(I)\ge 7$
$DT(I)\le 14$ e $z(I)\ge 7$
$DT(I)=14$ e $z(I)=7$
Spiegazione. Il circuito euleriano dell'albero raddoppiato è lungo $2d(T)=14$ e le scorciatoie non lo allungano; togliendo un lato dal giro ottimo si ottiene un albero, quindi $d(T)\le z(I)$.
Nell'algoritmo di Christofides per il TSP metrico, si aggiunge all'albero ricoprente minimo $T$ un matching perfetto minimo sulle città di grado dispari in $T$. In una stella con un centro e $3$ foglie (grado del centro $3$, delle foglie $1$), quante sono queste città?
$0$
$4$
$3$
$1$
Spiegazione. Il centro ha grado $3$ e le tre foglie grado $1$: tutte e quattro sono dispari. In ogni grafo il numero di vertici di grado dispari è pari, quindi il matching perfetto esiste.
Per ogni istanza del TSP, metrica o no, la lunghezza $d(T)$ di un albero ricoprente minimo è al più la lunghezza $z(I)$ del giro ottimo. Quale argomento lo dimostra?
Togliendo un lato dal giro ottimo si ottiene un cammino che tocca tutte le città, cioè un albero ricoprente, di lunghezza al più $z(I)$
La disuguaglianza triangolare permette di accorciare l'albero
Il giro ottimo contiene sempre l'albero ricoprente minimo
Raddoppiando l'albero si ottiene il giro ottimo
Spiegazione. Il cammino è un albero ricoprente, e $T$ è il più corto fra gli alberi ricoprenti; le distanze sono positive, quindi togliere un lato non allunga. Non serve la metrica.
Nel TSP metrico, sia $O$ un insieme pari di città e $M$ un matching perfetto minimo di $O$. Perché $d(M)\le z(I)/2$?
Perché $M$ ha la metà dei lati del giro ottimo
Perché ogni lato di $M$ è più corto di ogni lato del giro
Perché $M$ è contenuto nell'albero ricoprente minimo
Il giro ottimo, accorciato alle sole città di $O$, si divide in due matching perfetti di $O$ a lati alterni; il più corto è lungo al più $z(I)/2$
Spiegazione. Per la disuguaglianza triangolare il giro ristretto a $O$ non è più lungo di $z(I)$; i suoi lati, presi a uno a uno alternati, formano due matching perfetti, e il minimo è al più la metà.
Nel TSP metrico, l'algoritmo di Christofides usa un albero ricoprente minimo $T$ con $d(T)=10$ e un matching perfetto minimo $M$ con $d(M)=4$, e restituisce un giro di lunghezza $CH(I)=14$. Che cosa si sa del giro ottimo $z(I)$?
$\frac{28}{3}\le z(I)\le 10$
$z(I)\ge 14$
$10\le z(I)\le 14$
$z(I)=14$
Spiegazione. Il giro di $CH$ è ammissibile, quindi $z(I)\le 14$; $d(T)\le z(I)$ dà $z(I)\ge 10$ (più forte di $14/\frac32\approx 9{,}33$ e di $2d(M)=8$).
Nel TSP metrico esistono istanze $I_n$, con $n\ge 5$ dispari, su cui l'albero doppio $DT$ ha rapporto esattamente $\frac{2n}{n+2}$. Quanto vale con $n=7$, e a che cosa tende?
$2$ per ogni $n$
$\frac{14}{9}$, e tende a $2$
$\frac{14}{9}$, e tende a $\frac32$
$\frac{7}{9}$, e tende a $1$
Spiegazione. $\frac{2\cdot 7}{7+2}=\frac{14}{9}\approx 1{,}56$; per $n\to+\infty$ il rapporto tende a $2$, quindi la garanzia $2$ di $DT$ non si può migliorare.
Nel TSP metrico un cammino chiuso $W$ che visita ogni città almeno una volta si trasforma in un giro $\sigma$ saltando le città già visitate (scorciatoie). Perché $L(\sigma)$ non supera la lunghezza di $W$?
Per la disuguaglianza triangolare ogni scorciatoia $d_{u_0u_q}$ è al più la lunghezza del tratto di $W$ che sostituisce
Perché $\sigma$ ha meno città di $W$
Perché le distanze sono tutte uguali
Vale per ogni istanza del TSP, anche non metrica
Spiegazione. $d_{u_0u_q}\le d_{u_0u_1}+d_{u_1u_q}\le\dots$; senza disuguaglianza triangolare una scorciatoia può allungare il giro. È il passo chiave del double tree e di Christofides.
Nel TSP metrico, l'algoritmo del doppio albero e quello di Christofides partono entrambi da un albero ricoprente minimo $T$. Come rendono euleriano il multigrafo?
Entrambi raddoppiano gli spigoli di $T$
Doppio albero: aggiunge un abbinamento; Christofides: raddoppia $T$
Nessuno dei due usa un multigrafo euleriano
Doppio albero: raddoppia gli spigoli di $T$; Christofides: aggiunge un abbinamento perfetto di costo minimo sulle città di grado dispari di $T$
Spiegazione. Raddoppiare costa $2d(T)\le2z$; l'abbinamento costa al più $z/2$, da cui le garanzie $2$ e $\frac32$. In entrambi i casi il cammino euleriano si accorcia con le scorciatoie.
Per l'algoritmo di Christofides esistono istanze metriche $I_n$ ($n$ dispari) con $CH(I_n)/z(I_n)\to\frac32$. Nella costruzione l'MST è il cammino $1,2,\dots,n$, le città di grado dispari sono solo $1$ e $n$, e l'abbinamento è il lato $\{1,n\}$, lungo. Che cosa mostra?
Che il double tree è migliore di Christofides
Che le scorciatoie possono allungare il giro
Che la garanzia $\frac32$ di Christofides è stretta: l'abbinamento può costare quasi metà del giro ottimo
Che Christofides è sempre ottimo
Spiegazione. Il ciclo $1,\dots,n,1$ costa circa $\frac32 z(I_n)$, mentre il giro ottimo avanza di due città alla volta. Nessun rapporto migliore vale per tutte le istanze.
La garanzia $CH(I)\le\frac32z(I)$ di Christofides usa la disuguaglianza triangolare. Che cosa succede per il TSP generale, senza questa ipotesi?
Il TSP generale diventa polinomiale
Nessun algoritmo polinomiale ha un rapporto costante, se P $\ne$ NP
Christofides resta una $\frac32$-approssimazione
Christofides diventa una $2$-approssimazione
Spiegazione. Senza la disuguaglianza triangolare le scorciatoie possono costare moltissimo, e una garanzia costante permetterebbe di decidere l'esistenza di un ciclo hamiltoniano.
Per mostrare che il TSP non ha $\alpha$-approssimazioni polinomiali, da un grafo $G$ con $n$ vertici si costruisce un'istanza con $d_{ij}=1$ se $\{i,j\}$ è uno spigolo di $G$ e $d_{ij}=\lceil\alpha n\rceil+1$ altrimenti. Con $\alpha=2$ e $n=10$, quanto è lungo almeno ogni giro se $G$ non ha un ciclo hamiltoniano?
$21$
$20$
$29$
$30$
Spiegazione. Ogni giro usa almeno una coppia non adiacente ($21$) e altri $9$ spigoli lunghi almeno $1$: $9+21=30>\alpha n=20$. Se $G$ è hamiltoniano, $z=10$ e l'algoritmo darebbe al più $20$.
La dimostrazione che il TSP generale non ha rapporto costante (se $P\neq NP$) usa distanze $1$ sugli spigoli di un grafo $G$ e $\lceil\alpha n\rceil+1$ sulle altre coppie. Perché non dice nulla sul TSP metrico (disuguaglianza triangolare $d_{ij}\le d_{ik}+d_{kj}$)?
Perché il ciclo hamiltoniano è facile sui grafi metrici
Perché nel TSP metrico le distanze possono essere $0$
Le istanze costruite violano la disuguaglianza triangolare
Perché il TSP metrico si risolve in tempo polinomiale
Spiegazione. Se $\{i,k\},\{k,j\}\in E$ e $\{i,j\}\notin E$, allora $d_{ij}=\lceil\alpha n\rceil+1>2=d_{ik}+d_{kj}$. La dimostrazione ha bisogno di distanze così grandi; il TSP metrico resta NP-difficile.
Un'istanza del TSP è metrica se $d_{ij}\le d_{ik}+d_{kj}$ per ogni terna di città distinte. Nell'istanza di riferimento $d_{15}=9$, $d_{12}=5$ e $d_{25}=4$. La terna $(1,2,5)$ viola la condizione?
No: la condizione riguarda solo le città vicine
No: vale $9\le5+4$, con l'uguaglianza ammessa
Sì: $d_{15}$ non è strettamente minore di $d_{12}+d_{25}$
Sì: $d_{15}$ è la distanza più grande dell'istanza
Spiegazione. La disuguaglianza triangolare è $\le$, non $<$: $9=5+4$ la soddisfa. Andare da $1$ a $5$ passando per $2$ non costa meno del collegamento diretto, e le scorciatoie restano non più lunghe.
Nel TSP metrico (distanze con la disuguaglianza triangolare) l'algoritmo del doppio albero e quello di Christofides hanno rapporto costante. Che ruolo ha la disuguaglianza triangolare nelle loro garanzie?
Le scorciatoie (saltare città già visitate) non allungano il cammino
Rende il TSP risolvibile in tempo polinomiale
Garantisce che l'albero ricoprente minimo sia già un giro
Garantisce che il giro ottimo sia lungo al più $2n$
Spiegazione. Saltare le città interne di un tratto sostituisce il tratto con un solo spigolo, non più lungo per la disuguaglianza triangolare. Il TSP metrico resta NP-difficile.
TSP metrico con $4$ città: $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$. L'algoritmo di Kruskal esamina gli spigoli per distanza non decrescente (pareggi per coppia di indici) e prende quelli che non chiudono cicli. Quale albero ricoprente minimo $T$ trova?
$\{1,2\},\{3,4\},\{1,4\}$, con $d(T)=8$
$\{1,2\},\{1,3\},\{2,3\}$, con $d(T)=8$
$\{1,2\},\{3,4\}$, con $d(T)=4$
$\{1,2\},\{3,4\},\{1,3\}$, con $d(T)=7$
Spiegazione. Prende $\{1,2\}$ e $\{3,4\}$ ($2$), poi $\{1,3\}$ ($3$, prima di $\{2,3\}$ per la regola dei pareggi), che collega tutto. $\{1,2\},\{1,3\},\{2,3\}$ è un ciclo; due spigoli non ricoprono $4$ città.
Nel TSP metrico, il doppio albero e Christofides trasformano un cammino chiuso $W$ in un giro con le scorciatoie: si segue $W$ e si tiene ogni città solo alla sua prima occorrenza. Da $W=(1,2,1,3,4,3,1)$ quale giro si ottiene?
$(1,3,4,2)$
$(1,2,1,3,4)$
$(1,2,3,4)$
$(1,2,4,3)$
Spiegazione. Le prime occorrenze, in ordine, sono $1,2,3,4$; le ripetizioni di $1$ e $3$ si saltano e il giro torna a $1$. $(1,2,1,3,4)$ non è un giro: ripete la città $1$.
TSP metrico con $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$ e albero ricoprente minimo $T=\{\{1,2\},\{1,3\},\{3,4\}\}$. Il doppio albero visita $T$ in profondità dalla città $1$ (figli in ordine crescente) e tiene le città in ordine di prima visita. Quale giro dà, e quanto è lungo?
$(1,2,4,3)$, lungo $12$
$(1,2,3,4)$, lungo $11$
$(1,2,3,4)$, lungo $14$
$(1,3,4,2)$, lungo $12$
Spiegazione. Visita: $1,2,1,3,4,3,1$ (lunghezza $2d(T)=14$); le prime occorrenze danno $(1,2,3,4)$: $2+3+2+4=11\le14$. $14$ è il circuito senza scorciatoie.
Nel doppio albero per il TSP metrico si raddoppiano gli spigoli dell'albero ricoprente minimo e si segue un circuito euleriano con la regola di Fleury (si evita un ponte degli spigoli non usati, se c'è un'alternativa). Perché il circuito è una visita in profondità dell'albero?
L'ultima copia dello spigolo verso il padre è un ponte, usata per ultima
Perché l'algoritmo di Kruskal restituisce sempre un cammino
Perché nell'albero raddoppiato ogni città ha grado $2$
Perché Fleury sceglie sempre il vicino più lontano
Spiegazione. Finché resta un figlio da visitare, tornare al padre attraverserebbe un ponte: Fleury scende prima nei figli. Il giro è quindi il preordine dell'albero.
TSP metrico con $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$, albero minimo $T=\{\{1,2\},\{1,3\},\{3,4\}\}$. Christofides aggiunge un abbinamento perfetto minimo $M$ sulle città di grado dispari in $T$ e segue un circuito euleriano da $1$ (vicino di indice minimo). Quale giro dà?
$(1,2,3,4)$, lungo $11$
$(1,3,4,2)$, lungo $15$
$(1,2,1,3,4)$, lungo $14$
$(1,2,4,3)$, lungo $12$
Spiegazione. Gradi dispari: $2$ e $4$, quindi $M=\{\{2,4\}\}$ ($5$). $T\cup M$ è il ciclo $1,2,4,3,1$, di lunghezza $7+5=12$, senza scorciatoie. Il giro ottimo $(1,2,3,4)$ è lungo $11$: qui Christofides non lo trova, il doppio albero sì.
Nell'algoritmo di Christofides per il TSP metrico, $O$ è l'insieme delle città di grado dispari nell'albero ricoprente minimo $T$, e si cerca un abbinamento perfetto di $O$. Perché $|O|$ è sempre pari?
Perché le foglie di un albero sono sempre in numero pari
Perché l'algoritmo blossom lo richiede
I gradi di un grafo sommano al doppio del numero di spigoli
Perché $T$ ha $n-1$ spigoli e $n$ è dispari
Spiegazione. La somma dei gradi è pari, quindi le città di grado dispari sono in numero pari; nel grafo completo un abbinamento perfetto di $O$ esiste. Un albero può avere un numero dispari di foglie (stella con $3$ foglie).
In un'istanza del TSP metrico l'albero ricoprente minimo pesa $d(T)=20$ e un abbinamento perfetto minimo di un insieme pari di città pesa $d(M)=9$. Valgono $d(T)\le z(I)$ e $d(M)\le z(I)/2$ ($z(I)$ = lunghezza del giro ottimo). Quale lower bound su $z(I)$ se ne ricava?
$z(I)\ge14.5$
$z(I)\ge20$
$z(I)\ge29$
$z(I)\ge18$
Spiegazione. I due bound danno $z\ge20$ e $z\ge18$: vale il più forte, $20$. Sommarli ($29$) è un errore: $T$ e $M$ non sono parti disgiunte di un giro.
Per il doppio albero nel TSP metrico esistono istanze $I_n$ ($n$ dispari): la città $1$ dista $a=n$ da tutte, due foglie distano $b=n+1$ se consecutive in un cammino $P$ e $2a$ altrimenti. Perché $DT(I_n)=2(n-1)a$?
L'MST è la stella; foglie consecutive in preordine non sono unite da $P$
Perché l'albero minimo è il cammino $P$, percorso due volte
Perché le scorciatoie fanno risparmiare $b-a$ a ogni passo
Perché l'ottimo è lungo $(n-1)a$ e $DT$ ne è il doppio
Spiegazione. Ogni spigolo pesa almeno $a$ e solo quelli dal centro valgono $a$: l'MST è la stella. Il preordine è $(1,2,\dots,n)$ e indici consecutivi non sono mai consecutivi in $P$: $a+(n-2)2a+a$. L'ottimo vale $(n+2)(n-1)$.
Da quale problema NP-completo si riduce per mostrare che il TSP generale non ha rapporto costante (se $P\neq NP$)?
Il ciclo hamiltoniano
Il bin packing
La $2$-colorabilità
L'albero ricoprente minimo
Spiegazione. Si dà distanza $1$ agli spigoli del grafo e una distanza molto grande alle altre coppie: un rapporto $\alpha$ distinguerebbe i grafi hamiltoniani.
Nello scheduling $P\,||\,C_{\max}$ ($m$ macchine, durate $t_j$, makespan ottimo $z(I)$), $LIST$ assegna ogni lavoro della lista alla macchina meno carica. Sia $\ell$ un lavoro che finisce per ultimo, con inizio $S_\ell$. Quali fatti servono per dimostrare $LIST(I)\le\left(2-\frac1m\right)z(I)$?
Spiegazione. $LIST(I)=S_\ell+t_\ell\le\frac1m\sum_j t_j+\left(1-\frac1m\right)t_\ell\le\left(2-\frac1m\right)z(I)$. L'ordinamento serve solo per la garanzia migliore di $LPT$.
Nello scheduling $P\,||\,C_{\max}$, $LPT$ ordina i lavori per durata non crescente e assegna ciascuno alla macchina meno carica; la sua garanzia è $\frac43-\frac1{3m}$. Quanto vale con $m=2$ macchine?
$\frac43$
$\frac54$
$\frac76$
$\frac32$
Spiegazione. $\frac43-\frac1{3m}=\frac43-\frac16=\frac76$. Con una lista qualsiasi $LIST$ garantisce $2-\frac12=\frac32$.
Nello scheduling $P\,||\,C_{\max}$ con $m$ macchine, $LIST$ (lista qualsiasi, macchina meno carica) garantisce $2-\frac1m$ e $LPT$ (lista per durata non crescente) garantisce $\frac43-\frac1{3m}$. Quale affermazione è corretta?
Nessuna delle due è raggiunta: i rapporti sono solo approcciati al crescere di $n$
Entrambe sono tight: per ogni $m\ge 2$ esistono istanze che raggiungono esattamente i due rapporti
Entrambe sono tight solo per $m=2$; per $m\ge 3$ i rapporti sono più bassi
La garanzia di $LIST$ è tight, quella di $LPT$ no: il suo rapporto vero è più basso
Spiegazione. Le famiglie di istanze di Graham raggiungono esattamente i due rapporti per ogni $m\ge 2$ (per $LPT$: $2m+1$ lavori, con due lavori di ogni durata da $2m-1$ a $m$ più uno di durata $m$).
Scheduling $P\,||\,C_{\max}$ con $m=3$ macchine. $LIST$ assegna ogni lavoro, nell'ordine della lista, alla macchina meno carica (a parità quella di indice minore); $LPT$ fa lo stesso con la lista ordinata per durata non crescente. Con la lista $t=(2,3,4,6,2,2)$, quanto valgono i makespan di $LIST$ e di $LPT$?
$8$ e $8$
$9$ e $7$
$8$ e $7$
$7$ e $7$
Spiegazione. $LIST$: $2,3,4$ sulle tre macchine, $6$ sulla prima ($8$), poi $2$ sulla seconda ($5$) e $2$ sulla terza ($6$): makespan $8$. $LPT$ con $(6,4,3,2,2,2)$ dà carichi $(6,6,7)$, e $\lceil 19/3\rceil=7$ dimostra che è ottimo.
Nello scheduling $P\,||\,C_{\max}$, $LIST$ assegna i lavori nell'ordine di una lista data e $LPT$ li ordina prima per durata non crescente. Quale differenza pratica c'è fra i due algoritmi?
$LPT$ è esponenziale, $LIST$ polinomiale
$LIST$ può lavorare online, assegnando i lavori man mano che arrivano; $LPT$ deve conoscere tutti i lavori per ordinarli
$LIST$ richiede di conoscere tutti i lavori, $LPT$ no
$LPT$ usa la macchina più carica, $LIST$ la meno carica
Spiegazione. Entrambi usano la regola della macchina meno carica; l'ordinamento costa $O(n\log n)$ e richiede tutti i dati, ma abbassa la garanzia da $2-\frac1m$ a $\frac43-\frac1{3m}$.
Nello scheduling $P\,||\,C_{\max}$ con $m$ macchine, sia $\ell$ un lavoro che finisce per ultimo nello schedule di $LIST$, con inizio $S_\ell$. Perché $S_\ell\le\frac1m\sum_{j\ne\ell}t_j$?
$\ell$ va sulla macchina meno carica, il cui carico è al più la media dei carichi, che contengono solo lavori diversi da $\ell$
Perché $\ell$ è il lavoro più lungo
Perché i lavori sono ordinati per durata non crescente
Perché $S_\ell$ è sempre nullo
Spiegazione. Quando $\ell$ viene assegnato, la macchina scelta ha il carico minimo, e il minimo è al più la media dei carichi in quel momento, che sommano lavori diversi da $\ell$. Non serve nessun ordine della lista.
Nello scheduling $P\,||\,C_{\max}$ con $m=3$ macchine, $LIST$ produce uno schedule in cui il lavoro $\ell$, di durata $t_\ell=4$, finisce per ultimo; gli altri lavori hanno durata totale $15$. Quale limite superiore si ottiene sul makespan di $LIST$?
$19$
$5$
$\frac{19}{3}$
$9$
Spiegazione. $S_\ell\le\frac{15}{3}=5$, quindi $LIST(I)=S_\ell+t_\ell\le 9$. Con $z(I)\ge\frac{19}{3}$ e $z(I)\ge 4$ si ritrova la garanzia $2-\frac1m$.
Nello scheduling $P\,||\,C_{\max}$ con $m=3$ macchine, la lista contiene $m(m-1)=6$ lavori di durata $1$ seguiti da un lavoro di durata $m=3$. Quanto valgono il makespan di $LIST$ e quello ottimo?
$5$ e $4$: rapporto $\frac54$
$6$ e $3$: rapporto $2$
$5$ e $3$: rapporto $\frac53=2-\frac13$
$3$ e $3$: $LIST$ è ottimo
Spiegazione. $LIST$ distribuisce i lavori brevi, $2$ per macchina, poi il lavoro lungo finisce a $2+3=5$. L'ottimo mette il lavoro lungo da solo e $3$ lavori brevi su ciascuna delle altre: $3$. La garanzia è raggiunta.
Scheduling $P\,||\,C_{\max}$ con $m=3$ macchine e durate $t=(5,5,4,4,3,3,3)$. $LPT$ assegna i lavori in quest'ordine alla macchina meno carica (a parità, indice minore). Quanto valgono il makespan di $LPT$ e quello ottimo?
$12$ e $9$
$11$ e $9$: rapporto $\frac{11}{9}=\frac43-\frac19$
$9$ e $9$: $LPT$ è ottimo
$11$ e $10$
Spiegazione. $LPT$: $5,5,4$ sulle tre macchine, $4\to M_3$ ($8$), $3\to M_1$ ($8$), $3\to M_2$ ($8$), l'ultimo $3\to M_1$ ($11$). L'ottimo è $\{5,4\},\{5,4\},\{3,3,3\}$ con makespan $9$.
Nello scheduling $P\,||\,C_{\max}$, il lower bound $\mathrm{LB}=\max\{\max_jt_j,\ \frac1m\sum_jt_j\}$ vale per il makespan ottimo. Che relazione c'è fra il makespan di $LIST$ e $\mathrm{LB}$?
Spiegazione. L'ultimo lavoro inizia entro la media degli altri e dura al più $\max_jt_j$; entrambi i termini sono al più $\mathrm{LB}$. Una stima più fine dà $2-\frac1m$.
Nello scheduling $P\,||\,C_{\max}$ con $m=2$ macchine e durate $t=(1,1,2)$ in quest'ordine, quanto valgono il makespan di $LIST$ (lista data, macchina meno carica, a parità indice minore) e di $LPT$?
$LIST$ $3$, $LPT$ $3$
$LIST$ $4$, $LPT$ $2$
$LIST$ $3$, $LPT$ $2$
$LIST$ $2$, $LPT$ $2$
Spiegazione. $LIST$: $1\to M_1$, $1\to M_2$, $2\to M_1$: carichi $(3,1)$. $LPT$: $2\to M_1$, $1\to M_2$, $1\to M_2$: carichi $(2,2)$, ottimo. Mettere prima i lavori lunghi evita di lasciarli per ultimi.
Nel capitolo sull'approssimazione di $P\,||\,C_{\max}$, $z(I)$ è il makespan ottimo e $\mathscr{A}(I)$ quello di un'euristica. Quali due lower bound su $z(I)$ si usano nelle dimostrazioni delle garanzie?
$z(I)\ge m$ e $z(I)\ge n$
$z(I)\ge\mathscr{A}(I)$
$z(I)\ge\max_jt_j$ e $z(I)\ge\frac1m\sum_jt_j$
$z(I)\ge\min_jt_j$ e $z(I)\ge\sum_jt_j$
Spiegazione. Il lavoro più lungo sta su una macchina, e il carico massimo è almeno la media dei carichi. Combinati con l'ultimo lavoro assegnato danno la garanzia $2-\frac1m$ di $LIST$.
La garanzia di $LPT$ per $P\,||\,C_{\max}$ è $\frac43-\frac1{3m}$, migliore di $2-\frac1m$ di $LIST$. Quale ipotesi sull'ordine dei lavori la rende possibile?
Le macchine hanno velocità diverse
I lavori sono esaminati per durata non crescente, quindi l'ultimo lavoro assegnato è corto rispetto all'ottimo
I lavori sono esaminati in ordine casuale
I lavori hanno tutti la stessa durata
Spiegazione. Se il lavoro che determina il makespan è il più corto, o $z(I)$ è piccolo e la soluzione è ottima, o il lavoro pesa al più $z(I)/3$. Con un ordine qualsiasi l'ultimo lavoro può essere il più lungo.
List scheduling ($LIST$) per $P\,||\,C_{\max}$ assegna i lavori, nell'ordine della lista, alla macchina di carico minimo (a parità, indice minimo). Con $m=2$ e la lista di tempi $(2,3,4,5)$, che makespan ottiene?
In $LIST$ per $P\,||\,C_{\max}$, il lavoro $j$ inizia all'istante $S_j$ pari al carico della sua macchina al momento dell'assegnamento. Perché, quando l'ultimo lavoro inizia, tutte le macchine sono occupate almeno fino a $S_j$?
Perché la lista è ordinata per tempi decrescenti
Perché le macchine sono vuote all'inizio
Perché il lavoro più lungo è sempre l'ultimo
Il lavoro va sulla macchina di carico minimo
Spiegazione. $S_j$ è il minimo dei carichi: le altre macchine finiscono non prima. È l'osservazione su cui si costruisce la garanzia di $LIST$.
In uno schedule di $LIST$ per $P\,||\,C_{\max}$, il lavoro $\ell$ che termina per ultimo inizia in $S_\ell\le\frac1m\sum_{j\neq\ell}t_j$. Con $m=3$, $\sum_jt_j=27$ e $t_\ell=3$, quale limite si ottiene su $S_\ell$ e sul makespan?
$S_\ell\le24$, makespan $\le27$
$S_\ell\le8$, makespan $\le11$
$S_\ell\le9$, makespan $\le12$
$S_\ell\le8$, makespan $\le8$
Spiegazione. $S_\ell\le(27-3)/3=8$ e il makespan è $S_\ell+t_\ell\le11$. $9=27/3$ dimentica di togliere il lavoro $\ell$.
Da $S_\ell\le\frac1m\sum_{j\neq\ell}t_j$ ($\ell$ lavoro che termina per ultimo in $LIST$) si ricava $LIST(I)\le\frac1m\sum_jt_j+(1-\frac1m)t_\ell$. Quali due fatti danno poi $LIST(I)\le(2-\frac1m)z(I)$?
$\frac1m\sum_jt_j\le z(I)$ e $t_\ell\le z(I)$
$t_\ell\le\frac1m\sum_jt_j$ e $z(I)\le\sum_jt_j$
$LIST$ è ottimo per $m=1$ e $t_\ell\le1$
$S_\ell\le z(I)$ e $m\ge2$
Spiegazione. Sono i due termini del lower bound $\max\{\max_jt_j,\sum_jt_j/m\}\le z(I)$: sommando $z+(1-\frac1m)z$ si ottiene $2-\frac1m$.
Spiegazione. Con i lavori per durata decrescente, se il lavoro critico è lungo l'ottimo ne mette pochi per macchina e $LPT$ è ottimo; altrimenti è corto.
Le istanze tight di $LPT$ hanno $2m+1$ lavori. Quanti lavori hanno con $m=3$?
$7$
$6$
$9$
$4$
Spiegazione. $2\cdot3+1=7$: due per ogni durata da $2m-1$ a $m+1$ e tre di durata $m$.
Domande generate (16)
Ogni generatore crea a ogni avvio un'istanza nuova, con numeri diversi: qui alcuni esempi.
1. Principi degli algoritmi di approssimazione (2)
Esempio 1 · aa-g-approx-interval · livello facile · dispensa
Un algoritmo $\mathscr{A}$ è una $\alpha$-approssimazione, con $\alpha=\frac{4}{3}$, per un problema di massimo: $z(I)\le\alpha\,\mathscr{A}(I)$ per ogni istanza $I$, dove $z(I)$ è il valore ottimo. Su un'istanza $I$ restituisce $\mathscr{A}(I)=96$. Che cosa si può concludere sul valore ottimo $z(I)$?
$72\le z(I)\le 128$
$72\le z(I)\le 96$
$96\le z(I)\le 128$
$z(I)=128$
Spiegazione. Per un problema di massimo $z(I)/\mathscr{A}(I)\le\alpha$ e $\mathscr{A}(I)\le z(I)$, quindi $\mathscr{A}(I)\le z(I)\le\alpha\,\mathscr{A}(I)$.
Esempio 2 · aa-g-approx-interval · livello facile · dispensa
Un algoritmo $\mathscr{A}$ è una $\alpha$-approssimazione, con $\alpha=2$, per un problema di massimo: $z(I)\le\alpha\,\mathscr{A}(I)$ per ogni istanza $I$, dove $z(I)$ è il valore ottimo. Su un'istanza $I$ restituisce $\mathscr{A}(I)=8$. Che cosa si può concludere sul valore ottimo $z(I)$?
$z(I)=16$
$4\le z(I)\le 16$
$4\le z(I)\le 8$
$8\le z(I)\le 16$
Spiegazione. Per un problema di massimo $z(I)/\mathscr{A}(I)\le\alpha$ e $\mathscr{A}(I)\le z(I)$, quindi $\mathscr{A}(I)\le z(I)\le\alpha\,\mathscr{A}(I)$.
Esempio 1 · aa-g-approx-error · livello facile · dispensa
Per un problema di massimo un algoritmo trova una soluzione di valore $\mathscr{A}(I)=15$ e il valore ottimo è $z(I)=27$. Il rapporto di prestazione è $z(I)/\mathscr{A}(I)$ e l'errore relativo $|\mathscr{A}(I)-z(I)|/z(I)$. Quanto valgono, nell'ordine?
$\frac{9}{5}$ e $\frac{4}{5}$
$\frac{5}{9}$ e $\frac{4}{9}$
$\frac{9}{5}$ e $\frac{4}{9}$
$\frac{4}{9}$ e $\frac{9}{5}$
Spiegazione. Rapporto $\frac{9}{5}\ge 1$ ed errore $\frac{4}{9}$; l'errore si divide per il valore ottimo, non per quello trovato.
Esempio 2 · aa-g-approx-error · livello facile · dispensa
Per un problema di minimo un algoritmo trova una soluzione di valore $\mathscr{A}(I)=41$ e il valore ottimo è $z(I)=36$. Il rapporto di prestazione è $\mathscr{A}(I)/z(I)$ e l'errore relativo $|\mathscr{A}(I)-z(I)|/z(I)$. Quanto valgono, nell'ordine?
$\frac{5}{36}$ e $\frac{41}{36}$
$\frac{41}{36}$ e $\frac{5}{41}$
$\frac{36}{41}$ e $\frac{5}{36}$
$\frac{41}{36}$ e $\frac{5}{36}$
Spiegazione. Rapporto $\frac{41}{36}\ge 1$ ed errore $\frac{5}{36}$; l'errore si divide per il valore ottimo, non per quello trovato.
2. Algoritmi di approssimazione per lo zaino (3)
Esempio 1 · aa-g-kp-extgreedy · livello facile · dispensa
Problema dello zaino 0-1 (KP: si sceglie un sottoinsieme di oggetti di profitto massimo con peso totale al più $c$) con capacità $c=12$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 8 & 12 & 19 & 15 & 18\\ w_j & 1 & 7 & 9 & 7 & 5\end{array}$. L'algoritmo Ext-Greedy restituisce il migliore fra la soluzione del greedy per efficienza $p_j/w_j$ non crescente (pari merito: indice minore) e il miglior oggetto singolo. Quanto vale $GR^e(I)$?
$33$
$27$
$26$
$20$
Spiegazione. $GR$ (per efficienza non crescente) vale $26$; il miglior oggetto singolo ha profitto $19$; $GR^e(I)=\max\{26,19\}=26$. Il valore ottimo è $z(I)=33$.
Esempio 2 · aa-g-kp-extgreedy · livello facile · dispensa
Problema dello zaino 0-1 (KP: si sceglie un sottoinsieme di oggetti di profitto massimo con peso totale al più $c$) con capacità $c=12$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 15 & 10 & 13 & 18 & 12\\ w_j & 9 & 5 & 3 & 1 & 8\end{array}$. L'algoritmo Ext-Greedy restituisce il migliore fra la soluzione del greedy per efficienza $p_j/w_j$ non crescente (pari merito: indice minore) e il miglior oggetto singolo. Quanto vale $GR^e(I)$?
$33$
$43$
$41$
$28$
Spiegazione. $GR$ (per efficienza non crescente) vale $41$; il miglior oggetto singolo ha profitto $18$; $GR^e(I)=\max\{41,18\}=41$. Il valore ottimo è $z(I)=43$.
Esempio 1 · aa-g-kp-fptas · livello media · dispensa
Problema dello zaino 0-1 (KP: si sceglie un sottoinsieme di oggetti di profitto massimo con peso totale al più $c$) con capacità $c=9$ e $n=4$ oggetti ordinati per efficienza non crescente: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 17 & 10 & 7 & 12\\ w_j & 2 & 4 & 3 & 6\end{array}$. Il Basic-FPTAS $FP^{\varepsilon}$, con $\varepsilon=\frac{1}{2}$, scala i profitti con il fattore $K=\varepsilon\,GR^e(I)/n$, dove $GR^e(I)$ è il valore di Ext-Greedy (migliore fra greedy per efficienza e miglior oggetto singolo). Quali sono i profitti scalati $p'_j=\lfloor p_j/K\rfloor$?
$p'=(1,0,0,0)$
$p'=(4,3,2,3)$
$p'=(4,2,1,2)$
$p'=(8,4,3,5)$
Spiegazione. $GR^e(I)=34$, $K=\varepsilon\,GR^e(I)/n=\frac{17}{4}$ e $p'_j=\lfloor p_j/K\rfloor$: $p'=(4,2,1,2)$. Si arrotonda per difetto e il fattore usa $GR^e(I)$ e $n$.
Esempio 2 · aa-g-kp-fptas · livello media · dispensa
Problema dello zaino 0-1 (KP: si sceglie un sottoinsieme di oggetti di profitto massimo con peso totale al più $c$) con capacità $c=12$ e $n=4$ oggetti ordinati per efficienza non crescente: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 36 & 35 & 28 & 9\\ w_j & 3 & 3 & 5 & 3\end{array}$. Il Basic-FPTAS $FP^{\varepsilon}$, con $\varepsilon=\frac{1}{4}$, scala i profitti con il fattore $K=\varepsilon\,GR^e(I)/n$, dove $GR^e(I)$ è il valore di Ext-Greedy (migliore fra greedy per efficienza e miglior oggetto singolo). Quali sono i profitti scalati $p'_j=\lfloor p_j/K\rfloor$?
$p'=(5,5,4,1)$
$p'=(6,6,5,2)$
$p'=(1,1,1,0)$
$p'=(16,15,12,4)$
Spiegazione. $GR^e(I)=99$, $K=\varepsilon\,GR^e(I)/n=\frac{99}{16}$ e $p'_j=\lfloor p_j/K\rfloor$: $p'=(5,5,4,1)$. Si arrotonda per difetto e il fattore usa $GR^e(I)$ e $n$.
Esempio 1 · aa-g-kp-fptas-full · livello complessa · dispensa
Zaino 0/1 con capacità $c=9$ e oggetti ordinati per efficienza non crescente: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 22 & 25 & 31 & 11 & 16\\ w_j & 2 & 3 & 4 & 2 & 3\end{array}$. L'algoritmo Basic-FPTAS con $\varepsilon=\frac12$ calcola $GR^e(I)=\max\{GR(I),\max_jp_j\}$ ($GR$: greedy per efficienza, che salta gli oggetti che non entrano), pone $K=\varepsilon\,GR^e(I)/n$ e $p'_j=\lfloor p_j/K\rfloor$, risolve all'ottimo l'istanza con profitti $p'_j$ e restituisce il profitto originale $FP^{\varepsilon}(I)$ della soluzione trovata. Quanto valgono $FP^{\varepsilon}(I)$ e il valore ottimo $z(I)$?
$FP^{\varepsilon}(I)=8$, $z(I)=78$
$FP^{\varepsilon}(I)=78$, $z(I)=79$
$FP^{\varepsilon}(I)=78$, $z(I)=156$
$FP^{\varepsilon}(I)=78$, $z(I)=78$
Spiegazione. $GR^e(I)=78$, $K=\frac{39}{5}$, $p'=(2,3,3,1,2)$. L'istanza scalata ha ottimo $8$ con gli oggetti $\{1,2,3\}$, di profitto originale $78$; l'ottimo vero è $78$, e infatti $78\ge\frac12\cdot78$.
Esempio 2 · aa-g-kp-fptas-full · livello complessa · dispensa
Zaino 0/1 con capacità $c=13$ e oggetti ordinati per efficienza non crescente: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 36 & 35 & 29 & 32 & 11\\ w_j & 4 & 4 & 6 & 7 & 3\end{array}$. L'algoritmo Basic-FPTAS con $\varepsilon=\frac12$ calcola $GR^e(I)=\max\{GR(I),\max_jp_j\}$ ($GR$: greedy per efficienza, che salta gli oggetti che non entrano), pone $K=\varepsilon\,GR^e(I)/n$ e $p'_j=\lfloor p_j/K\rfloor$, risolve all'ottimo l'istanza con profitti $p'_j$ e restituisce il profitto originale $FP^{\varepsilon}(I)$ della soluzione trovata. Quanto valgono $FP^{\varepsilon}(I)$ e il valore ottimo $z(I)$?
$FP^{\varepsilon}(I)=82$, $z(I)=164$
$FP^{\varepsilon}(I)=9$, $z(I)=82$
$FP^{\varepsilon}(I)=82$, $z(I)=82$
$FP^{\varepsilon}(I)=82$, $z(I)=83$
Spiegazione. $GR^e(I)=82$, $K=\frac{41}{5}$, $p'=(4,4,3,3,1)$. L'istanza scalata ha ottimo $9$ con gli oggetti $\{1,2,5\}$, di profitto originale $82$; l'ottimo vero è $82$, e infatti $82\ge\frac12\cdot82$.
3. Algoritmi di approssimazione per il bin packing (3)
Esempio 1 · aa-g-bpp-anyfit · livello facile · dispensa
Bin packing (BPP: oggetti in contenitori di capacità $c$, minimizzando i contenitori) con $c=10$ e pesi, nell'ordine di esame, $w=(7,4,3,7,3,6,4)$. I contenitori sono numerati nell'ordine di apertura; a parità di capacità residua si sceglie quello di indice minore. Quale vettore $bin$ (contenitore di ogni oggetto) produce First Fit (FF)?
$bin=(1,2,2,3,1,4,4)$
$bin=(1,2,2,3,3,4,4)$
$bin=(1,2,1,3,3,2,4)$
$bin=(1,2,1,3,2,4,4)$
Spiegazione. FF dà $bin=(1,2,1,3,2,4,4)$ con $4$ contenitori. NF tiene aperto un solo contenitore; FF sceglie il primo in cui l'oggetto entra, BF quello con capacità residua minima, WF quello con capacità residua massima.
Esempio 2 · aa-g-bpp-anyfit · livello facile · dispensa
Bin packing (BPP: oggetti in contenitori di capacità $c$, minimizzando i contenitori) con $c=10$ e pesi, nell'ordine di esame, $w=(3,7,6,5,7,4,3)$. I contenitori sono numerati nell'ordine di apertura; a parità di capacità residua si sceglie quello di indice minore. Quale vettore $bin$ (contenitore di ogni oggetto) produce Next Fit (NF)?
$bin=(1,1,2,3,4,2,4)$
$bin=(1,1,2,3,4,2,3)$
$bin=(1,1,2,3,4,5,5)$
$bin=(1,1,2,3,4,3,2)$
Spiegazione. NF dà $bin=(1,1,2,3,4,5,5)$ con $5$ contenitori. NF tiene aperto un solo contenitore; FF sceglie il primo in cui l'oggetto entra, BF quello con capacità residua minima, WF quello con capacità residua massima.
Esempio 1 · aa-g-bpp-nf · livello facile · dispensa
Bin packing con capacità $c=10$ e oggetti di peso $(4,2,1,6,6,6,8,3)$ in quest'ordine. Next Fit (NF) tiene aperto un solo contenitore e ne apre uno nuovo quando l'oggetto non entra. Quanti contenitori usa NF, e quanto vale il bound sul peso $\lceil\sum_jw_j/c\rceil$, nell'ordine?
$4$, $6$
$6$, $5$
$5$, $4$
$6$, $4$
Spiegazione. NF usa $6$ contenitori e il bound vale $\lceil 36/10\rceil=4$; First Fit, che riprende i contenitori già aperti, ne usa $5$. Vale sempre $NF(I)\le 2z(I)$.
Esempio 2 · aa-g-bpp-nf · livello facile · dispensa
Bin packing con capacità $c=10$ e oggetti di peso $(4,7,3,1,4,7,7,6)$ in quest'ordine. Next Fit (NF) tiene aperto un solo contenitore e ne apre uno nuovo quando l'oggetto non entra. Quanti contenitori usa NF, e quanto vale il bound sul peso $\lceil\sum_jw_j/c\rceil$, nell'ordine?
$6$, $4$
$5$, $4$
$6$, $5$
$4$, $6$
Spiegazione. NF usa $6$ contenitori e il bound vale $\lceil 39/10\rceil=4$; First Fit, che riprende i contenitori già aperti, ne usa $5$. Vale sempre $NF(I)\le 2z(I)$.
Esempio 1 · aa-g-bpp-anyfit-full · livello complessa · dispensa
Bin packing con contenitori di capacità $c=10$ e oggetti, nell'ordine di input, di peso $w=(5,3,2,6,6,6,8,4)$. Next Fit (NF) tiene aperto solo l'ultimo contenitore; First Fit (FF), Best Fit (BF) e Worst Fit (WF) mettono ogni oggetto, rispettivamente, nel primo contenitore in cui entra, in quello con capacità residua minima e in quello con capacità residua massima fra quelli in cui entra (pari merito: indice minore), e aprono un contenitore nuovo solo se non entra in nessuno. Quanti contenitori usa ciascun algoritmo?
$NF=5$, $FF=5$, $BF=5$, $WF=5$
$NF=6$, $FF=5$, $BF=5$, $WF=6$
$NF=5$, $FF=6$, $BF=5$, $WF=5$
$NF=6$, $FF=5$, $BF=5$, $WF=5$
Spiegazione. Simulando le quattro regole: $NF=6$, $FF=5$, $BF=5$, $WF=5$; il bound sul peso è $\lceil40/10\rceil=4$. NF non è Any Fit: chiude un contenitore anche se un oggetto successivo vi entrerebbe.
Esempio 2 · aa-g-bpp-anyfit-full · livello complessa · dispensa
Bin packing con contenitori di capacità $c=10$ e oggetti, nell'ordine di input, di peso $w=(4,7,4,2,4,8,7,6)$. Next Fit (NF) tiene aperto solo l'ultimo contenitore; First Fit (FF), Best Fit (BF) e Worst Fit (WF) mettono ogni oggetto, rispettivamente, nel primo contenitore in cui entra, in quello con capacità residua minima e in quello con capacità residua massima fra quelli in cui entra (pari merito: indice minore), e aprono un contenitore nuovo solo se non entra in nessuno. Quanti contenitori usa ciascun algoritmo?
$NF=6$, $FF=5$, $BF=5$, $WF=5$
$NF=5$, $FF=6$, $BF=5$, $WF=5$
$NF=6$, $FF=5$, $BF=5$, $WF=6$
$NF=5$, $FF=5$, $BF=5$, $WF=5$
Spiegazione. Simulando le quattro regole: $NF=6$, $FF=5$, $BF=5$, $WF=5$; il bound sul peso è $\lceil42/10\rceil=5$. NF non è Any Fit: chiude un contenitore anche se un oggetto successivo vi entrerebbe.
4. Colorazione dei vertici: limiti dell'approssimazione (2)
Esempio 1 · aa-g-vci-interval · livello facile · dispensa
Grafo di intervalli con i vertici $1,\dots,6$ e gli intervalli chiusi $I_{1}=[1,5]$, $I_{2}=[5,8]$, $I_{3}=[6,9]$, $I_{4}=[7,11]$, $I_{5}=[8,9]$, $I_{6}=[8,9]$ (due vertici sono adiacenti se i loro intervalli si intersecano). Quanti colori usa la colorazione greedy con i vertici in ordine di estremo sinistro non decrescente?
$3$
$4$
$5$
$6$
Spiegazione. Su un grafo di intervalli quell'ordine dà $\omega(G)$ colori, il massimo numero di intervalli con un punto in comune: qui $5$, ed è ottimo perché $\chi(G)\ge\omega(G)$. Il bound $\Delta(G)+1=6$ vale per ogni ordine ma è più debole.
Esempio 2 · aa-g-vci-interval · livello facile · dispensa
Grafo di intervalli con i vertici $1,\dots,6$ e gli intervalli chiusi $I_{1}=[3,4]$, $I_{2}=[3,7]$, $I_{3}=[3,7]$, $I_{4}=[6,10]$, $I_{5}=[7,10]$, $I_{6}=[9,13]$ (due vertici sono adiacenti se i loro intervalli si intersecano). Quanti colori usa la colorazione greedy con i vertici in ordine di estremo sinistro non decrescente?
$3$
$5$
$4$
$6$
Spiegazione. Su un grafo di intervalli quell'ordine dà $\omega(G)$ colori, il massimo numero di intervalli con un punto in comune: qui $4$, ed è ottimo perché $\chi(G)\ge\omega(G)$. Il bound $\Delta(G)+1=5$ vale per ogni ordine ma è più debole.
Esempio 1 · aa-g-vci-planar · livello facile · dispensa
Un grafo semplice ha $n=19$ vertici e $m=60$ spigoli. Usando il lemma sul numero di spigoli dei grafi planari, che cosa si può dire?
$3n-6=51$: può essere planare
$3n-6=51$: non è planare
$3n-6=54$: non è planare
$3n-6=54$: può essere planare
Spiegazione. Ogni grafo planare con $n\ge3$ vertici ha $m\le3n-6=51$. Qui $m>51$: il grafo non è planare.
Esempio 2 · aa-g-vci-planar · livello facile · dispensa
Un grafo semplice ha $n=14$ vertici e $m=52$ spigoli. Usando il lemma sul numero di spigoli dei grafi planari, che cosa si può dire?
$3n-6=39$: può essere planare
$3n-6=39$: non è planare
$3n-6=36$: non è planare
$3n-6=36$: può essere planare
Spiegazione. Ogni grafo planare con $n\ge3$ vertici ha $m\le3n-6=36$. Qui $m>36$: il grafo non è planare.
Esempio 1 · aa-g-cli-product · livello facile · dispensa
Due grafi sui vertici $\{1,2,3,4\}$: $G$ con $E=\{\{2,4\}\}$ e $H$ con $F=\{\{2,3\},\{3,4\}\}$. Quanti vertici ha il prodotto forte $G\boxtimes H$ e quanto vale il suo numero di clique?
$16$ vertici e $\omega=5$
$16$ vertici e $\omega=2$
$16$ vertici e $\omega=4$
$8$ vertici e $\omega=4$
Spiegazione. $G\boxtimes H$ ha $4\cdot4=16$ vertici e $\omega(G\boxtimes H)=\omega(G)\,\omega(H)=2\cdot2=4$: il prodotto di due clique è una clique, e ogni clique del prodotto sta in un tale prodotto.
Esempio 2 · aa-g-cli-product · livello facile · dispensa
Due grafi sui vertici $\{1,2,3,4\}$: $G$ con $E=\{\{1,3\}\}$ e $H$ con $F=\{\{1,2\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$. Quanti vertici ha il prodotto forte $G\boxtimes H$ e quanto vale il suo numero di clique?
$8$ vertici e $\omega=6$
$16$ vertici e $\omega=5$
$16$ vertici e $\omega=3$
$16$ vertici e $\omega=6$
Spiegazione. $G\boxtimes H$ ha $4\cdot4=16$ vertici e $\omega(G\boxtimes H)=\omega(G)\,\omega(H)=2\cdot3=6$: il prodotto di due clique è una clique, e ogni clique del prodotto sta in un tale prodotto.
Esempio 1 · aa-g-cli-maximal · livello facile · dispensa
Grafo con i vertici $1,\dots,8$ e $E=\{\{1,6\},\{2,5\},\{2,7\},\{2,8\},\{3,4\},\{3,5\},\{3,6\},\{3,8\},\{4,8\},\{5,7\},\{6,7\},\{6,8\},\{7,8\}\}$. L'algoritmo greedy esamina i vertici in ordine $1,2,\dots,8$ e aggiunge un vertice a $S$ se non è adiacente a nessun vertice già in $S$. Quanto vale $|S|$, e qual è il lower bound $\lceil n/(\Delta(G)+1)\rceil$ che vale per ogni insieme stabile massimale?
$|S|=3$, bound $3$
$|S|=2$, bound $2$
$|S|=4$, bound $2$
$|S|=3$, bound $2$
Spiegazione. Il greedy trova $S=\{1,2,3\}$, massimale. Con $\Delta(G)=5$ ogni vertice di $S$ esclude al più $\Delta(G)$ vicini, quindi $|S|\ge\lceil 8/6\rceil=2$ e $\alpha(G)/|S|\le\Delta(G)+1$.
Esempio 2 · aa-g-cli-maximal · livello facile · dispensa
Grafo con i vertici $1,\dots,8$ e $E=\{\{1,4\},\{1,5\},\{3,4\},\{4,5\},\{4,8\},\{5,6\},\{5,7\},\{5,8\},\{6,7\}\}$. L'algoritmo greedy esamina i vertici in ordine $1,2,\dots,8$ e aggiunge un vertice a $S$ se non è adiacente a nessun vertice già in $S$. Quanto vale $|S|$, e qual è il lower bound $\lceil n/(\Delta(G)+1)\rceil$ che vale per ogni insieme stabile massimale?
$|S|=5$, bound $2$
$|S|=4$, bound $2$
$|S|=5$, bound $3$
$|S|=6$, bound $2$
Spiegazione. Il greedy trova $S=\{1,2,3,6,8\}$, massimale. Con $\Delta(G)=5$ ogni vertice di $S$ esclude al più $\Delta(G)$ vicini, quindi $|S|\ge\lceil 8/6\rceil=2$ e $\alpha(G)/|S|\le\Delta(G)+1$.
6. TSP: il caso generale e il caso metrico (2)
Esempio 1 · aa-g-tsp-mst · livello facile · dispensa
TSP metrico con $5$ città e distanze (di Manhattan fra punti del piano, tutte diverse) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 12 & 10 & 7 & 4\\ 2 & 12 & - & 2 & 5 & 16\\ 3 & 10 & 2 & - & 3 & 14\\ 4 & 7 & 5 & 3 & - & 11\\ 5 & 4 & 16 & 14 & 11 & -\end{array}$. Quanto è lungo un albero ricoprente minimo $T$, il cui valore $d(T)$ è un lower bound sul giro ottimo?
$15$
$17$
$32$
$16$
Spiegazione. L'algoritmo di Prim (o di Kruskal) dà $d(T)=16$. Togliendo un lato dal giro ottimo si ottiene un albero ricoprente, quindi $d(T)\le z(I)$; l'albero doppio dà un giro lungo al più $2d(T)=32$.
Esempio 2 · aa-g-tsp-mst · livello facile · dispensa
TSP metrico con $5$ città e distanze (di Manhattan fra punti del piano, tutte diverse) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 5 & 6 & 14 & 16\\ 2 & 5 & - & 3 & 11 & 13\\ 3 & 6 & 3 & - & 8 & 10\\ 4 & 14 & 11 & 8 & - & 2\\ 5 & 16 & 13 & 10 & 2 & -\end{array}$. Quanto è lungo un albero ricoprente minimo $T$, il cui valore $d(T)$ è un lower bound sul giro ottimo?
$34$
$15$
$18$
$36$
Spiegazione. L'algoritmo di Prim (o di Kruskal) dà $d(T)=18$. Togliendo un lato dal giro ottimo si ottiene un albero ricoprente, quindi $d(T)\le z(I)$; l'albero doppio dà un giro lungo al più $2d(T)=36$.
Esempio 1 · aa-g-tsp-dt · livello media · dispensa
TSP metrico con $5$ città e distanze (di Manhattan fra punti del piano, tutte diverse) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 4 & 5 & 9 & 6\\ 2 & 4 & - & 1 & 13 & 10\\ 3 & 5 & 1 & - & 12 & 11\\ 4 & 9 & 13 & 12 & - & 7\\ 5 & 6 & 10 & 11 & 7 & -\end{array}$. L'algoritmo dell'albero doppio prende l'albero ricoprente minimo (unico), ne raddoppia i lati, lo percorre in profondità dalla città $1$ visitando i figli per indice crescente e salta le città già visitate: il giro è l'ordine di prima visita. Quanto è lungo?
$18$
$36$
$33$
$32$
Spiegazione. L'albero ha $d(T)=18$; l'ordine di prima visita è $(1,2,3,5,4)$, lungo $32\le 2d(T)=36$: le scorciatoie non allungano il cammino perché le distanze sono metriche.
Esempio 2 · aa-g-tsp-dt · livello media · dispensa
TSP metrico con $5$ città e distanze (di Manhattan fra punti del piano, tutte diverse) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 5 & 6 & 14 & 16\\ 2 & 5 & - & 3 & 11 & 13\\ 3 & 6 & 3 & - & 8 & 10\\ 4 & 14 & 11 & 8 & - & 2\\ 5 & 16 & 13 & 10 & 2 & -\end{array}$. L'algoritmo dell'albero doppio prende l'albero ricoprente minimo (unico), ne raddoppia i lati, lo percorre in profondità dalla città $1$ visitando i figli per indice crescente e salta le città già visitate: il giro è l'ordine di prima visita. Quanto è lungo?
$18$
$35$
$34$
$36$
Spiegazione. L'albero ha $d(T)=18$; l'ordine di prima visita è $(1,2,3,4,5)$, lungo $34\le 2d(T)=36$: le scorciatoie non allungano il cammino perché le distanze sono metriche.
7. Approssimazione per $P\|C_{\max}$ (2)
Esempio 1 · aa-g-pcmax-list · livello facile · dispensa
Scheduling $P\,||\,C_{\max}$ con $m=3$ macchine identiche e durate, nell'ordine della lista, $t=(6,8,1,8,2,3,1)$. $LIST$ assegna ogni lavoro alla macchina meno carica (a parità quella di indice minore) nell'ordine della lista; $LPT$ fa lo stesso dopo aver ordinato i lavori per durata non crescente. Quanto valgono i makespan di $LIST$ e di $LPT$, nell'ordine?
$11$, $11$
$10$, $11$
$10$, $10$
$11$, $10$
Spiegazione. $LIST$ dà $11$ e $LPT$ dà $10$; il lower bound $\lceil\sum_jt_j/m\rceil$ vale $10$.
Esempio 2 · aa-g-pcmax-list · livello facile · dispensa
Scheduling $P\,||\,C_{\max}$ con $m=3$ macchine identiche e durate, nell'ordine della lista, $t=(4,8,3,1,4,8,8)$. $LIST$ assegna ogni lavoro alla macchina meno carica (a parità quella di indice minore) nell'ordine della lista; $LPT$ fa lo stesso dopo aver ordinato i lavori per durata non crescente. Quanto valgono i makespan di $LIST$ e di $LPT$, nell'ordine?
$16$, $12$
$12$, $16$
$12$, $12$
$16$, $16$
Spiegazione. $LIST$ dà $16$ e $LPT$ dà $12$; il lower bound $\lceil\sum_jt_j/m\rceil$ vale $12$.
Esempio 1 · aa-g-pcmax-ratio · livello media · dispensa
Scheduling $P\,||\,C_{\max}$ con $m=2$ macchine identiche e durate $t=(2,8,3,2,9,6)$. $LPT$ ordina i lavori per durata non crescente e assegna ciascuno alla macchina meno carica (a parità, indice minore). Quanto vale il rapporto $LPT(I)/z(I)$, con $z(I)$ makespan ottimo?
$\frac{15}{16}$
$\frac{7}{6}$
$\frac{16}{15}$
$1$
Spiegazione. $LPT(I)=16$ e $z(I)=15$: rapporto $\frac{16}{15}$, al più la garanzia $\frac43-\frac1{3m}=\frac{7}{6}$.
Esempio 2 · aa-g-pcmax-ratio · livello media · dispensa
Scheduling $P\,||\,C_{\max}$ con $m=2$ macchine identiche e durate $t=(9,2,9,6,7,7)$. $LPT$ ordina i lavori per durata non crescente e assegna ciascuno alla macchina meno carica (a parità, indice minore). Quanto vale il rapporto $LPT(I)/z(I)$, con $z(I)$ makespan ottimo?
$\frac{7}{6}$
$\frac{10}{11}$
$\frac{11}{10}$
$\frac{22}{21}$
Spiegazione. $LPT(I)=22$ e $z(I)=20$: rapporto $\frac{11}{10}$, al più la garanzia $\frac43-\frac1{3m}=\frac{7}{6}$.