← Torna al sito

Banca delle domande

357 domande fisse · 16 domande generate

Domande fisse (357)

1. Principi degli algoritmi di approssimazione (64)

aa-f-001 · livello facile · dispensa
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)$?
  1. $\alpha=\frac43$
  2. $\alpha=\frac54$
  3. $\alpha=\frac34$
  4. $\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$.
aa-f-002 · livello facile · dispensa
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)}$?
  1. $\frac56$ e $20\%$
  2. $\frac65$ e $2$
  3. $\frac56$ e $16{,}7\%$
  4. $\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$.
aa-f-003 · livello teorema · dispensa
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?
  1. In un PTAS e in un FPTAS il tempo è polinomiale per ogni $\varepsilon$ fissato, e in nessuno dei due in $\frac1\varepsilon$
  2. Un tempo $O(n^{1/\varepsilon})$ è polinomiale sia nella dimensione sia in $\frac1\varepsilon$, quindi dà un FPTAS
  3. In un PTAS il tempo è polinomiale per ogni $\varepsilon$ fissato; in un FPTAS è polinomiale anche in $\frac1\varepsilon$
  4. 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.
aa-f-004 · livello facile · dispensa
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?
  1. Che ogni costante maggiore di $\frac32$ è una garanzia relativa di $\mathscr{A}$
  2. Che nessuna costante minore di $\frac32$ è una garanzia relativa di $\mathscr{A}$
  3. Che $\frac32$ è una garanzia relativa di $\mathscr{A}$, valida per ogni istanza
  4. 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.
aa-f-027 · livello facile · dispensa
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?
  1. $4$
  2. $\frac{9}{5}$
  3. $\frac54$
  4. $\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.
aa-f-028 · livello teorema · dispensa
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?
  1. $r(\mathscr{A})$ è sempre raggiunto da qualche istanza
  2. $\mathscr{A}$ è una $\alpha$-approssimazione se e solo se $\alpha\ge r(\mathscr{A})$
  3. $\mathscr{A}$ è una $\alpha$-approssimazione se e solo se $\alpha=r(\mathscr{A})$
  4. $\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.
aa-f-029 · livello facile · dispensa
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?
  1. $\beta=2$, perché $\chi(G)\ge 3$
  2. $\beta=5$, il numero di colori usati
  3. $\beta=\frac53$, il rapporto fra colori usati e numero cromatico
  4. $\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.
aa-f-030 · livello facile · dispensa
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)$?
  1. $\mathscr{A}(I)/z(I)\le\beta$ per ogni istanza
  2. $\mathscr{A}(I)/z(I)\ge 1+\beta$ per ogni istanza
  3. Nulla: le due garanzie sono indipendenti
  4. $\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.
aa-f-031 · livello facile · dispensa
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)$?
  1. $30\le z(I)\le 60$
  2. $z(I)\le 15$
  3. $15\le z(I)\le 30$
  4. $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.
aa-f-032 · livello facile · dispensa
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$?
  1. Che diventi esponenziale per ogni $\varepsilon<\frac12$
  2. Che cresca: un errore ammesso più piccolo richiede più tempo
  3. Che diminuisca: con $\varepsilon$ piccolo ci sono meno soluzioni da esaminare
  4. 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$.
aa-f-033 · livello facile · dispensa
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?
  1. $O(n^2/\varepsilon)$
  2. $O(n^{1/\varepsilon})$
  3. $O(2^{1/\varepsilon}\,n)$
  4. $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$.
aa-f-034 · livello facile · dispensa
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}$?
  1. Da $O(n^2)$ a $O(n^{2/10})$: diminuisce
  2. Resta $O(n^2)$: l'esponente non dipende da $\varepsilon$
  3. Diventa esponenziale in $n$
  4. 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.
aa-f-090 · livello facile · dispensa
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à?
  1. Perché ogni problema di ottimizzazione ha valori positivi
  2. Perché $\mathscr{A}(I)$ deve essere uguale a $z(I)$
  3. Perché i valori negativi sono inammissibili
  4. 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.
aa-f-125 · livello facile · dispensa
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. $1.25$ in entrambi i casi
  2. $1.25$ e poi $0.8$
  3. $0.8$ e poi $1.25$
  4. $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.
aa-f-126 · livello facile · dispensa
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?
  1. Il rapporto fra il valore euristico e il valore ottimo
  2. Il tempo di calcolo nel caso peggiore
  3. La differenza fra il valore ottimo e un lower bound
  4. 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.
aa-f-127 · livello facile · dispensa
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?
  1. Almeno $53$
  2. Almeno $150$
  3. Almeno $47$
  4. Almeno $50/3$
Spiegazione. L'errore assoluto è al più $3$: $\mathscr{A}(I)\ge50-3$. $50/3$ confonde la garanzia assoluta con un rapporto.
aa-f-202 · livello facile · dispensa
Problema di minimo: l'ottimo vale $60$ e l'euristica trova $72$. Che rapporto di prestazione ottiene?
  1. $\frac56$
  2. $12$
  3. $\frac15$
  4. $\frac65$
Spiegazione. Per un problema di minimo il rapporto è $\mathscr{A}(I)/z(I)=72/60=\frac65$: è sempre almeno $1$.
aa-f-203 · livello facile · dispensa
Un problema di massimo ha $z(I)=30$ e un algoritmo $\mathscr{A}$ restituisce $\mathscr{A}(I)=20$. Quanto vale il rapporto di prestazione su $I$?
  1. $10$
  2. $\frac13$
  3. $\frac32$
  4. $\frac23$
Spiegazione. Per un problema di massimo il rapporto è $z(I)/\mathscr{A}(I)=30/20=\frac32$, scritto con l'ottimo al numeratore perché sia almeno $1$.
aa-f-204 · livello facile · dispensa
Se un algoritmo $\mathscr{A}$ restituisce sempre una soluzione ammissibile, che cosa si può dire del suo rapporto di prestazione su ogni istanza?
  1. Può essere negativo
  2. È almeno $1$
  3. È al più $1$
  4. È 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.
aa-f-205 · livello facile · dispensa
Un algoritmo per un problema di minimo ha $\mathscr{A}(I)\le 2z(I)$ su ogni istanza. Che cosa si può concludere?
  1. È un algoritmo di $2$-approssimazione
  2. È un algoritmo $2$-additivo
  3. Ha errore relativo al più $\frac12$
  4. È 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$.
aa-f-206 · livello facile · dispensa
Un algoritmo per un problema di massimo ha $\mathscr{A}(I)\ge\frac12 z(I)$ su ogni istanza. Di quale $\alpha$-approssimazione si tratta?
  1. $\alpha=\frac12$
  2. $\alpha=\frac32$
  3. Nessuna: per i problemi di massimo $\alpha$ è minore di $1$
  4. $\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.
aa-f-207 · livello facile · dispensa
Nella definizione di algoritmo di $\alpha$-approssimazione, che cosa deve valere per la costante $\alpha$?
  1. $0<\alpha<1$
  2. $\alpha$ è il rapporto di prestazione su una sola istanza
  3. $\alpha\ge1$ e non dipende dall'istanza
  4. $\alpha$ può dipendere dall'istanza
Spiegazione. $\alpha\in[1,+\infty)$ è una costante: la stessa disuguaglianza deve valere per tutte le istanze.
aa-f-208 · livello facile · dispensa
Che cosa rappresenta il rapporto di prestazione nel caso peggiore $r(\mathscr{A})$?
  1. Il minimo del rapporto di prestazione sulle istanze
  2. L'estremo superiore del rapporto di prestazione su tutte le istanze
  3. Il rapporto di prestazione sull'istanza più grande
  4. La media dei rapporti di prestazione sulle istanze
Spiegazione. $r(\mathscr{A})=\sup_I$ del rapporto: è la più piccola costante $\alpha$ per cui $\mathscr{A}$ è una $\alpha$-approssimazione.
aa-f-209 · livello facile · dispensa
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ù?
  1. Che la garanzia $\frac32$ è tight
  2. Che l'algoritmo è ottimo
  3. Che il problema non ha uno schema di approssimazione
  4. 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$.
aa-f-210 · livello facile · dispensa
Se il valore euristico supera l'ottimo al più di un'unità, su ogni istanza di un problema di minimo, che tipo di algoritmo è?
  1. Un algoritmo di $1$-approssimazione relativa
  2. Un algoritmo esatto per ogni istanza
  3. Un algoritmo di $2$-approssimazione relativa
  4. Un algoritmo di approssimazione $1$-additivo
Spiegazione. $\mathscr{A}(I)-z(I)\le\beta$ con $\beta=1$ per ogni istanza è la garanzia additiva; non è esatto, perché può sbagliare di uno.
aa-f-211 · livello facile · dispensa
Un problema di massimo ha $z(I)=17$; un algoritmo $2$-additivo può restituire, su questa istanza, quali valori?
  1. Solo $15$
  2. Ogni valore fra $\frac{17}{2}$ e $17$
  3. Ogni valore fra $15$ e $17$
  4. 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$.
aa-f-212 · livello facile · dispensa
Che cosa è l'errore additivo nel caso peggiore $e(\mathscr{A})$ di un algoritmo per un problema di minimo?
  1. $\sup_I\,(z(I)-\mathscr{A}(I))$
  2. $\sup_I\,(\mathscr{A}(I)-z(I))$
  3. $\max_I\,\mathscr{A}(I)/z(I)$
  4. $\inf_I\,(\mathscr{A}(I)-z(I))$
Spiegazione. È l'estremo superiore della differenza fra valore euristico e ottimo; per un problema di massimo si scambiano i due termini.
aa-f-213 · livello facile · dispensa
Per un problema di minimo, $z(I)=8$ e $\mathscr{A}(I)=10$. Quanto valgono l'errore additivo e l'errore relativo?
  1. $2$ e $\frac14$
  2. $2$ e $\frac15$
  3. $\frac54$ e $\frac14$
  4. $\frac14$ e $2$
Spiegazione. Errore additivo $\mathscr{A}(I)-z(I)=2$; errore relativo $(\mathscr{A}(I)-z(I))/z(I)=2/8=\frac14$ (si divide per l'ottimo).
aa-f-214 · livello facile · dispensa
Per un problema di massimo, $z(I)=50$ e $\mathscr{A}(I)=40$. Quanto vale l'errore relativo?
  1. $\frac14$
  2. $\frac54$
  3. $10$
  4. $\frac15$
Spiegazione. L'errore relativo divide sempre per l'ottimo: $(z(I)-\mathscr{A}(I))/z(I)=10/50=\frac15$.
aa-f-215 · livello facile · dispensa
Che cosa è uno schema di approssimazione per un problema $\mathscr{P}$?
  1. Un algoritmo esatto pseudo-polinomiale
  2. Una famiglia di istanze su cui una garanzia è stretta
  3. Una famiglia di algoritmi $\mathscr{A}_\varepsilon$
  4. 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.
aa-f-216 · livello facile · dispensa
Uno schema ha tempo $O(n^{1/\varepsilon})$. Di che cosa si tratta?
  1. Un algoritmo esatto polinomiale
  2. Un PTAS, ma non un FPTAS
  3. Un FPTAS
  4. 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.
aa-f-217 · livello facile · dispensa
A quale classe appartiene uno schema di approssimazione il cui algoritmo $\mathscr{A}_\varepsilon$ richiede $O(n^3/\varepsilon)$ operazioni?
  1. Un FPTAS (e quindi anche un PTAS)
  2. Un PTAS ma non un FPTAS
  3. Un algoritmo esponenziale
  4. Un algoritmo $\frac1\varepsilon$-additivo
Spiegazione. Il tempo è polinomiale sia nella taglia $n$ sia nell'accuratezza $\frac1\varepsilon$: è un FPTAS; ogni FPTAS è anche un PTAS.
aa-f-218 · livello facile · dispensa
Che cosa si chiama «accuratezza» di uno schema di approssimazione?
  1. L'errore relativo $\varepsilon$
  2. Il rapporto $1+\varepsilon$
  3. Il tempo di calcolo
  4. La quantità $\frac1\varepsilon$
Spiegazione. Più piccolo è $\varepsilon$, più grande è $\frac1\varepsilon$ e più precisa è la soluzione: per questo $\frac1\varepsilon$ si chiama accuratezza.
aa-f-219 · livello facile · dispensa
Uno schema per un problema di massimo ha errore relativo $\varepsilon=\frac14$. Che garanzia di approssimazione dà?
  1. $\varepsilon=\frac14$, cioè $\frac14$
  2. $1-\varepsilon=\frac34$
  3. $\frac{1}{1-\varepsilon}=\frac43$
  4. $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.
aa-f-220 · livello teorema · dispensa
Quale relazione lega il rapporto nel caso peggiore $r(\mathscr{A})$ alle garanzie relative di $\mathscr{A}$?
  1. $r(\mathscr{A})=1$ per ogni algoritmo ammissibile, qualunque sia la garanzia $\alpha$
  2. È la più piccola garanzia $\alpha$, cioè quella tight
  3. Ogni garanzia $\alpha$ di $\mathscr{A}$ è strettamente minore di $r(\mathscr{A})$, e nessuna garanzia è tight
  4. $r(\mathscr{A})$ è sempre finito, e ogni garanzia $\alpha\ge1$ è tight per $\mathscr{A}$
Spiegazione. Ogni garanzia è $\ge r(\mathscr{A})$ e $r(\mathscr{A})$ stesso è una garanzia (se finito): è la più piccola, cioè quella tight.
aa-f-221 · livello teorema · dispensa
Uno schema di approssimazione per un problema di minimo con errore relativo $\varepsilon$: che cosa garantisce ogni $\mathscr{A}_\varepsilon$?
  1. $\mathscr{A}_\varepsilon(I)\le(1+\varepsilon)z(I)$ su ogni istanza
  2. $\mathscr{A}_\varepsilon(I)\le z(I)+\varepsilon$
  3. $\mathscr{A}_\varepsilon(I)\ge(1-\varepsilon)z(I)$
  4. $\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.
aa-f-222 · livello teorema · dispensa
Che cosa significa $e(\mathscr{A})=\infty$ per un algoritmo $\mathscr{A}$?
  1. $\mathscr{A}$ non ha alcuna garanzia relativa finita
  2. $\mathscr{A}$ non termina
  3. $\mathscr{A}$ restituisce soluzioni inammissibili
  4. $\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.
aa-f-223 · livello teorema · dispensa
Quale relazione vale fra le classi di schemi di approssimazione?
  1. PTAS e FPTAS sono la stessa cosa
  2. Un FPTAS non è uno schema di approssimazione
  3. Ogni FPTAS è un PTAS, non viceversa
  4. 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.
aa-f-224 · livello ipotesi · dispensa
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?
  1. Che l'istanza abbia un'unica soluzione ottima
  2. Che restituisca sempre una soluzione ammissibile
  3. Che $\mathscr{A}$ sia un algoritmo polinomiale
  4. 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.
aa-f-225 · livello ipotesi · dispensa
Perché nel capitolo si suppone $z(I)>0$?
  1. Perché i rapporti dividono per $z(I)$
  2. Perché altrimenti il problema non ha soluzioni ammissibili
  3. Perché gli algoritmi greedy richiedono pesi positivi
  4. 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à.
aa-f-226 · livello ipotesi · dispensa
Un algoritmo ha $\mathscr{A}(I)\le 2z(I)$ su tutte le istanze tranne una famiglia infinita. È una $2$-approssimazione?
  1. Sì, se la famiglia è infinita ma rara
  2. Sì: basta che valga sulle istanze di riferimento
  3. Sì, se $r(\mathscr{A})<\infty$ sulle altre istanze
  4. 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$.
aa-f-227 · livello ipotesi · dispensa
Nella definizione di PTAS il tempo di $\mathscr{A}_\varepsilon$ deve essere polinomiale nella taglia dell'istanza: per quali $\varepsilon$?
  1. Solo per $\varepsilon=\frac12$
  2. Per nessun $\varepsilon$: basta che sia pseudo-polinomiale
  3. Per ogni $\varepsilon\in(0,1)$ fissato
  4. 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.
aa-f-228 · livello ipotesi · dispensa
Per dimostrare che una garanzia relativa $\alpha$ è tight, che cosa basta esibire?
  1. Un'istanza con rapporto maggiore di $\alpha$
  2. Un'istanza con rapporto esattamente $\alpha$
  3. Un'istanza su cui l'algoritmo è ottimo
  4. 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.
aa-f-229 · livello ipotesi · dispensa
Nella definizione di algoritmo $\beta$-additivo, che cosa si richiede a $\beta$?
  1. $\beta\ge0$ costante
  2. $\beta\ge1$
  3. $\beta$ proporzionale a $z(I)$
  4. $\beta$ dipendente dalla taglia dell'istanza
Spiegazione. $\beta\in[0,+\infty)$ è una costante; se dipendesse da $z(I)$ o dalla taglia non sarebbe più una garanzia additiva.
aa-f-316 · livello teorema · dispensa
Per un problema di minimo, che relazione c'è fra errore relativo $\varepsilon(I)$ e rapporto di prestazione $R(I)$?
  1. $R(I)=\varepsilon(I)$
  2. $R(I)=1+\varepsilon(I)$
  3. $R(I)=1-\varepsilon(I)$
  4. $R(I)=\frac{1}{1-\varepsilon(I)}$
Spiegazione. $\frac{\mathscr{A}(I)}{z(I)}=1+\frac{\mathscr{A}(I)-z(I)}{z(I)}$; per un problema di massimo $R(I)=\frac{1}{1-\varepsilon(I)}$.
aa-f-317 · livello teorema · dispensa
Per un problema di massimo, un errore relativo al più $\varepsilon$ equivale a quale rapporto?
  1. $\frac{z(I)}{\mathscr{A}(I)}\le\frac{1}{1-\varepsilon}$
  2. $\frac{z(I)}{\mathscr{A}(I)}\le1+\varepsilon$
  3. $\frac{\mathscr{A}(I)}{z(I)}\le1+\varepsilon$
  4. $z(I)-\mathscr{A}(I)\le\varepsilon$
Spiegazione. $\mathscr{A}(I)\ge(1-\varepsilon)z(I)$, cioè $z(I)/\mathscr{A}(I)\le\frac{1}{1-\varepsilon}$, che è più di $1+\varepsilon$.
aa-f-318 · livello teorema · dispensa
Che cosa significa $r(\mathscr{A})=\infty$?
  1. $\mathscr{A}$ non ha garanzia additiva
  2. $\mathscr{A}$ ha tempo esponenziale
  3. $\mathscr{A}$ è ottimo su ogni istanza
  4. $\mathscr{A}$ non ha garanzia relativa finita
Spiegazione. Il rapporto non è limitato da nessuna costante: $\mathscr{A}$ non è una $\alpha$-approssimazione per nessun $\alpha$.
aa-f-319 · livello teorema · dispensa
Uno schema di approssimazione per un problema di minimo dà, scelto $\varepsilon$, quale garanzia?
  1. Una garanzia additiva $\varepsilon$
  2. Una $2$-approssimazione
  3. Una $(1+\varepsilon)$-approssimazione
  4. Una $\varepsilon$-approssimazione
Spiegazione. Errore relativo $\le\varepsilon$ significa $\mathscr{A}_\varepsilon(I)\le(1+\varepsilon)z(I)$.
aa-f-320 · livello ipotesi · dispensa
Per un FPTAS il tempo deve essere polinomiale in quali quantità?
  1. Nel valore ottimo $z(I)$ e in $n$
  2. Nella taglia e in $\frac1\varepsilon$
  3. Solo nella taglia dell'istanza
  4. Solo nell'accuratezza $\frac1\varepsilon$
Spiegazione. Polinomiale in entrambe; solo nella taglia (per $\varepsilon$ fisso) basta per un PTAS.
aa-f-321 · livello ipotesi · dispensa
Uno schema di approssimazione richiede errore relativo al più $\varepsilon$: per quali $\varepsilon$?
  1. Per ogni $\varepsilon\in(0,1)$
  2. Per un solo $\varepsilon$ fissato
  3. Solo per $\varepsilon\ge\frac12$
  4. Per $\varepsilon=0$
Spiegazione. La famiglia contiene un algoritmo per ogni $\varepsilon\in(0,1)$: la precisione si sceglie a piacere.
aa-f-322 · livello ipotesi · dispensa
La garanzia additiva, a differenza di quella relativa, richiede $z(I)>0$?
  1. Sì, sempre
  2. Sì, solo per i problemi di massimo
  3. Sì, e anche $\mathscr{A}(I)>0$
  4. No: confronta una differenza
Spiegazione. $\mathscr{A}(I)-z(I)\le\beta$ ha senso anche con valori nulli o negativi; la positività serve ai rapporti.
aa-f-323 · livello ipotesi · dispensa
$r(\mathscr{A})=\frac32$ basta per dire che $\mathscr{A}$ è una $\frac32$-approssimazione?
  1. No: serve $r(\mathscr{A})<\frac32$
  2. Solo per i problemi di minimo
  3. Sì: ogni rapporto è al più l'estremo superiore
  4. No: serve anche un'istanza con rapporto $\frac32$
Spiegazione. Ogni rapporto è $\le\sup=\frac32$, anche se nessuna istanza lo raggiunge esattamente.
aa-f-336 · livello facile · dispensa
Quanto vale $z(I)/\mathscr{A}(I)$ se, in un problema di massimo, $z(I)=45$ e la soluzione euristica vale $36$?
  1. $\frac15$
  2. $\frac54$
  3. $\frac45$
  4. $9$
Spiegazione. Per un problema di massimo il rapporto è $z(I)/\mathscr{A}(I)=45/36=\frac54$.
aa-f-337 · livello facile · dispensa
Un algoritmo di $3$-approssimazione per un problema di minimo, su un'istanza con $z(I)=12$, che valori può restituire?
  1. Da $12$ a $36$
  2. Da $4$ a $12$
  3. Da $12$ a $15$
  4. Solo $36$
Spiegazione. $z(I)\le\mathscr{A}(I)\le3z(I)$: fra $12$ e $36$.
aa-f-338 · livello facile · dispensa
Massimizzazione, ottimo $18$: entro quale intervallo sta il valore trovato da una $2$-approssimazione?
  1. Da $18$ a $36$
  2. Da $16$ a $18$
  3. Solo $9$
  4. Da $9$ a $18$
Spiegazione. $z(I)/\mathscr{A}(I)\le2$ e $\mathscr{A}(I)\le z(I)$: fra $9$ e $18$.
aa-f-339 · livello facile · dispensa
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. $1$
  2. $\frac{23}{18}$
  3. $\frac32$
  4. $\frac43$
Spiegazione. $r(\mathscr{A})$ è l'estremo superiore dei rapporti su tutte le istanze, non la media: $\frac32$.
aa-f-340 · livello facile · dispensa
Un algoritmo sbaglia sempre di al più $3$ unità e su un'istanza sbaglia proprio di $3$. Quanto vale $e(\mathscr{A})$?
  1. $0$
  2. $3$
  3. $4$
  4. $\frac13$
Spiegazione. La garanzia additiva $3$ è raggiunta: è la più piccola possibile, quindi $e(\mathscr{A})=3$.
aa-f-341 · livello facile · dispensa
Uno schema per un problema di minimo con $\varepsilon=0{,}1$ garantisce quale valore su un'istanza con $z(I)=50$?
  1. Al più $55$
  2. Al più $50{,}1$
  3. Almeno $45$
  4. Esattamente $50$
Spiegazione. Errore relativo $\le0{,}1$: $\mathscr{A}_\varepsilon(I)\le1{,}1\cdot50=55$.
aa-f-342 · livello facile · dispensa
Uno schema ha tempo $O(2^{1/\varepsilon}n^2)$. Che cos'è?
  1. Un FPTAS, e quindi un PTAS
  2. Né un PTAS né un FPTAS
  3. Un algoritmo esatto polinomiale
  4. Un PTAS, non un FPTAS
Spiegazione. Per $\varepsilon$ fisso il tempo è polinomiale in $n$; la dipendenza da $\frac1\varepsilon$ è esponenziale, quindi non è un FPTAS.
aa-f-343 · livello facile · dispensa
Che cosa confonde chi chiama «$\varepsilon$-approssimazione» uno schema con errore relativo $\varepsilon$?
  1. Il minimo con il massimo
  2. Il tempo di calcolo con lo spazio
  3. L'errore con il rapporto
  4. Il PTAS con l'FPTAS
Spiegazione. Un errore relativo $\varepsilon$ dà rapporto $1+\varepsilon$ (minimo) o $\frac{1}{1-\varepsilon}$ (massimo), mai $\varepsilon<1$.
aa-f-344 · livello teorema · dispensa
Se $\mathscr{A}$ è una $\alpha$-approssimazione e $\alpha'>\alpha$, che cosa si può dire?
  1. $\mathscr{A}$ è esatto
  2. È anche una $\alpha'$-approssimazione
  3. $\mathscr{A}$ non è una $\alpha'$-approssimazione
  4. $r(\mathscr{A})=\alpha'$
Spiegazione. Se il rapporto è sempre $\le\alpha$, è anche $\le\alpha'$: le garanzie più deboli valgono tutte.
aa-f-345 · livello teorema · dispensa
Un algoritmo $\beta$-additivo per un problema di minimo con $z(I)\ge1$ su ogni istanza è anche relativo?
  1. Sì, una $(1+\beta)$-approssimazione
  2. No, mai, per nessun $\beta$
  3. Sì, una $\beta$-approssimazione
  4. Solo se $\beta=0$, cioè esatto
Spiegazione. $\mathscr{A}(I)\le z(I)+\beta\le z(I)+\beta z(I)=(1+\beta)z(I)$ se $z(I)\ge1$.
aa-f-346 · livello ipotesi · dispensa
Per dedurre da una garanzia additiva $\beta$ la garanzia relativa $1+\beta$ (minimo), quale ipotesi serve?
  1. $\beta<1$ e $\beta>0$
  2. Che $\mathscr{A}$ sia polinomiale
  3. Nessuna ipotesi
  4. $z(I)\ge1$ su ogni istanza
Spiegazione. Serve $\beta\le\beta z(I)$, cioè $z(I)\ge1$; con ottimi piccolissimi l'errore relativo può essere enorme.
aa-f-347 · livello ipotesi · dispensa
Il rapporto nel caso peggiore $r(\mathscr{A})$ si calcola su quali istanze?
  1. Su quelle con $n$ grande
  2. Su una sola istanza
  3. Su tutte le istanze del problema
  4. Sulle istanze di riferimento
Spiegazione. È un estremo superiore su tutte le istanze: è una misura di caso peggiore, non di caso medio.

2. Algoritmi di approssimazione per lo zaino (50)

aa-f-005 · livello teorema · dispensa
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?
  1. $GR$, $GR^e$ e $H^2$ hanno tutti rapporto $2$
  2. $GR$ non ha garanzia costante, $GR^e$ ha $r(GR^e)=2$, $H^2$ ha $r(H^2)=\frac43$
  3. $GR$ ha $r(GR)=2$ e $GR^e$ ha $r(GR^e)=\frac43$
  4. $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.
aa-f-006 · livello ipotesi · dispensa
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$?
  1. $z(I)\le\sum_{i<s}p_i+p_s$; $GR(I)\ge\sum_{i<s}p_i$; $p_{\max}\ge p_s$
  2. $z(I)\le\sum_{i<s}p_i+p_s$; $GR(I)\ge\sum_{i<s}p_i$; $p_{\max}\le p_s$
  3. $z(I)\le\sum_{i<s}p_i$; $GR(I)\ge\sum_{i\le s}p_i$; $p_{\max}\ge p_s$
  4. $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$.
aa-f-007 · livello facile · dispensa
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$?
  1. $\frac43$
  2. $\frac32$
  3. $\frac65$
  4. $\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.
aa-f-008 · livello facile · dispensa
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?
  1. Esiste un algoritmo polinomiale con garanzia assoluta $p_{\max}$, il profitto massimo di un oggetto
  2. Esiste un algoritmo polinomiale con garanzia assoluta $1$, ottenuto arrotondando il bound di Dantzig
  3. Un algoritmo con garanzia assoluta $k$ e tempo $O(f(n,c))$ risolverebbe all'ottimo ogni istanza nello stesso tempo
  4. 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.
aa-f-035 · livello facile · dispensa
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}$?
  1. $s=2$, $\mathit{rc}=0$
  2. $s=3$, $\mathit{rc}=3$
  3. $s=4$, $\mathit{rc}=0$
  4. $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.
aa-f-036 · livello facile · dispensa
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$?
  1. Perché altrimenti l'oggetto critico sarebbe il primo
  2. Perché altrimenti il greedy non termina
  3. Altrimenti tutti gli oggetti entrano, non c'è oggetto critico e prenderli tutti è ottimo
  4. 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.
aa-f-037 · livello facile · dispensa
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)$?
  1. $28$
  2. $23$
  3. $21$
  4. $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$.
aa-f-038 · livello teorema · dispensa
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)$?
  1. $\frac M2$, che cresce senza limite con $M$
  2. $2$, per ogni $M$
  3. $1$: $GR$ è ottimo
  4. $\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.
aa-f-039 · livello facile · dispensa
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)$?
  1. $2$, il valore di $GR$
  2. $M+2$, la somma dei profitti
  3. $\frac M2$
  4. $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.
aa-f-040 · livello facile · dispensa
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?
  1. Oggetti tutti uguali: $GR^e$ è sempre ottimo
  2. Un solo oggetto: il rapporto è $1$
  3. $c=2M$ e tre oggetti $(2,1)$, $(M,M)$, $(M,M)$: $GR^e$ vale circa $M$, l'ottimo $2M$
  4. $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$.
aa-f-041 · livello facile · dispensa
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?
  1. Sugli oggetti con profitto maggiore di $\max\{p_i,p_k\}$
  2. Sugli altri oggetti con profitto al più $\min\{p_i,p_k\}$ e peso al più la capacità residua
  3. Su tutti gli altri oggetti, qualunque sia il profitto
  4. 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}$.
aa-f-042 · livello facile · dispensa
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?
  1. $O(n^3)$, e $O(n^2)$ con un'implementazione più accurata
  2. $O(n\log n)$, come il greedy
  3. $O(2^n)$, perché prova sottoinsiemi
  4. $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$.
aa-f-043 · livello facile · dispensa
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$?
  1. $\frac54$ e $O(n^4)$
  2. $\frac65$ e $O(n^4)$
  3. $\frac43$ e $O(n^5)$
  4. $\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$.
aa-f-044 · livello facile · dispensa
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?
  1. $\ell=8$ e rapporto $\frac98$
  2. $\ell=9$ e rapporto $\frac{11}{10}$
  3. $\ell=8$ e rapporto $\frac{10}{9}$
  4. $\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.
aa-f-045 · livello facile · dispensa
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?
  1. Rapporto al più $5$, errore relativo al più $80\%$
  2. Rapporto al più $\frac54$, errore relativo al più $20\%$
  3. Rapporto al più $\frac65$, errore relativo al più $20\%$
  4. 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.
aa-f-046 · livello facile · dispensa
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$?
  1. I profitti scalati sono piccoli (dell'ordine di $n/\varepsilon$), e la PD sui profitti costa in proporzione al profitto totale
  2. Perché la PD sulla capacità non dipende dai profitti
  3. Perché l'istanza scalata ha meno oggetti
  4. 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.
aa-f-047 · livello ipotesi · dispensa
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?
  1. Dividere tutti i profitti per $k$ e arrotondare per difetto
  2. Aggiungere $k$ oggetti fittizi di profitto nullo
  3. Ridurre la capacità di $k$ unità
  4. 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$.
aa-f-091 · livello facile · dispensa
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?
  1. $\mathscr{A}(I)\ge z(I)$ e $\mathscr{A}(I)/z(I)\ge1$
  2. $\mathscr{A}(I)=z(I)$
  3. $\mathscr{A}(I)\le z(I)$ e $\mathscr{A}(I)/z(I)\ge1$
  4. $\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$.
aa-f-092 · livello facile · dispensa
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?
  1. Basta provare le coppie di oggetti più leggeri
  2. La coppia migliore è sempre quella di profitto totale massimo
  3. 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
  4. 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.
aa-f-093 · livello teorema · dispensa
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)$?
  1. $(\vartheta+2)/\vartheta$
  2. $\vartheta/2$, che cresce senza limite: $GR$ non ha garanzia costante
  3. $2$, per ogni $\vartheta$
  4. $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.
aa-f-094 · livello facile · dispensa
Perché il greedy $GR$ per efficienza può essere arbitrariamente lontano dall'ottimo dello zaino 0/1?
  1. Un oggetto piccolo e molto efficiente può occupare la capacità che servirebbe a un oggetto grande e redditizio
  2. Perché $GR$ non rispetta la capacità
  3. Perché $GR$ ordina gli oggetti per peso
  4. Non può: $GR$ è una $2$-approssimazione
Spiegazione. Con $c=\vartheta$, $(2,1)$ e $(\vartheta,\vartheta)$ il greedy vale $2$ e l'ottimo $\vartheta$. Il rimedio è $GR^e=\max\{GR,\max_jp_j\}$.
aa-f-095 · livello teorema · dispensa
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. $1$
  2. $\frac{\vartheta}{2}$
  3. $\frac32$
  4. $\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$.
aa-f-096 · livello teorema · dispensa
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?
  1. È minore di $1$
  2. Tende a $2$
  3. Tende a $\frac43$ per $M\to\infty$
  4. 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$.
aa-f-097 · livello facile · dispensa
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)?
  1. $z=40$, $H^2=22$
  2. $z=40$, $H^2=32$
  3. $z=40$, $H^2=40$
  4. $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$.
aa-f-098 · livello facile · dispensa
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$?
  1. $\frac43$ e $\frac65$
  2. $\frac32$ e $\frac54$
  3. $2$ e $\frac43$
  4. $\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.
aa-f-099 · livello teorema · dispensa
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?
  1. Perché il tempo è esponenziale in $n$ per ogni $\varepsilon$
  2. Perché non garantisce errore relativo $\varepsilon$
  3. È anche un FPTAS
  4. 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)$.
aa-f-100 · livello facile · dispensa
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$?
  1. $n^2$
  2. $n^6$
  3. $n^4$, perché $\ell=5-2=3$
  4. $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.
aa-f-101 · livello teorema · dispensa
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?
  1. $FP^{\varepsilon}(I)\ge z(I)-\varepsilon$
  2. $FP^{\varepsilon}(I)\ge(1-\varepsilon)\,z(I)$
  3. $FP^{\varepsilon}(I)=z(I)$
  4. $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)$.
aa-f-102 · livello ipotesi · dispensa
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?
  1. La garanzia $z(I)\le2\,GR^e(I)$ di Ext-Greedy limita il valore ottimo scalato a $2n/\varepsilon$
  2. Il fatto che i profitti scalati siano al più $1$
  3. Il fatto che $n\le Q$ sempre
  4. 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$.
aa-f-103 · livello facile · dispensa
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$?
  1. $20$
  2. $100$
  3. $2000$
  4. $200$
Spiegazione. $Q=\lfloor2\cdot10\cdot10\rfloor=200$, quindi circa $11\cdot201$ celle: il tempo $O(n^2/\varepsilon)$ non dipende dai profitti originali.
aa-f-124 · livello facile · dispensa
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?
  1. Tutti hanno rapporto $2$
  2. $GR$: $\frac43$; $GR^e$: nessuna costante; $H^2$: $2$; $H^{\ell}$: $\frac{\ell+1}{\ell}$
  3. $GR$: nessuna costante; $GR^e$: $2$; $H^2$: $\frac43$; $H^{\ell}$: $\frac{\ell+2}{\ell+1}$
  4. $GR$: $2$; $GR^e$: $\frac43$; $H^2$: $\frac32$; $H^{\ell}$: $1$
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.
aa-f-128 · livello facile · dispensa
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$?
  1. Perché ogni oggetto pesa più di $c/2$
  2. Non esiste sempre: dipende dai profitti
  3. In ordine, prima o poi il peso supera $c$
  4. 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.
aa-f-129 · livello teorema · dispensa
Nello zaino 0/1 (oggetti ordinati per efficienza, oggetto critico $s$) vale $z(I)\le\sum_{j<s}p_j+p_s$. Perché?
  1. Perché $p_s$ è il profitto massimo
  2. Perché $z(I)\le z(\mathrm{LP})\le\sum_{j<s}p_j+p_s$
  3. Perché l'ottimo contiene sempre l'oggetto critico
  4. Perché gli oggetti dopo $s$ non entrano mai nello zaino
Spiegazione. $z(\mathrm{LP})=\sum_{j<s}p_j+\mathit{rc}\,p_s/w_s$ e $\mathit{rc}<w_s$. È il primo passo della garanzia $2$ di Ext-Greedy.
aa-f-130 · livello facile · dispensa
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$?
  1. $16$
  2. $14$
  3. $19$
  4. $13$
Spiegazione. Prende $(8,4)$ e $(6,3)$ (peso $7$), salta $(5,5)$, prende $(2,2)$: $16$. $14$ si ferma all'oggetto critico.
aa-f-131 · livello facile · dispensa
Quanto tempo richiede l'algoritmo greedy $GR$ per lo zaino 0/1 con $n$ oggetti, compreso l'ordinamento per efficienza?
  1. $O(n)$
  2. $O(n^2)$
  3. $O(nc)$
  4. $O(n\log n)$
Spiegazione. L'ordinamento costa $O(n\log n)$ e la scansione $O(n)$. $O(nc)$ è il tempo pseudo-polinomiale della programmazione dinamica.
aa-f-132 · livello facile · dispensa
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?
  1. $GR=2$, Ext-Greedy $=12$
  2. $GR=12$, Ext-Greedy $=12$
  3. $GR=2$, Ext-Greedy $=10$
  4. $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.
aa-f-133 · livello teorema · dispensa
Per Ext-Greedy ($GR^e=\max\{GR,p_{\max}\}$) vale $z(I)/GR^e(I)\le2$. Quale catena di disuguaglianze lo dimostra ($s$ oggetto critico)?
  1. $z\le\sum_jp_j$ e $\sum_jp_j\le2\,GR^e$
  2. $z\le\sum_{j<s}p_j+p_s\le GR+p_{\max}\le2\,GR^e$
  3. $z\le GR+p_s$ e $p_s\le GR$, quindi $z\le2\,GR$
  4. $z\le n\,p_{\max}$ e $n\,p_{\max}\le2\,GR^e$
Spiegazione. $GR$ prende almeno gli oggetti prima di $s$, e $p_s\le p_{\max}$; entrambi gli addendi sono al più $GR^e$.
aa-f-134 · livello teorema · dispensa
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?
  1. Sono coerenti con la scommessa su $i$ e $k$
  2. Perché gli altri oggetti sono sempre più pesanti
  3. Per rendere ottima la soluzione greedy residua
  4. 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.
aa-f-135 · livello facile · dispensa
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$?
  1. $O(n^3)$
  2. $O(3n)$
  3. $O(2^n)$
  4. $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.
aa-f-136 · livello facile · dispensa
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?
  1. $O(nc)$
  2. $O(2^n)$
  3. $O(n)$
  4. $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.
aa-f-137 · livello facile · dispensa
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$?
  1. $K=0.5$, $p'_j=74$
  2. $K=2$, $p'_j=18$
  3. $K=2$, $p'_j=18.5$
  4. $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.
aa-f-138 · livello teorema · dispensa
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?
  1. Pesi e capacità non cambiano: i vincoli sono gli stessi
  2. Perché i profitti scalati sono minori di quelli originali
  3. Perché si scalano anche i pesi con lo stesso fattore
  4. 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.
aa-f-139 · livello facile · dispensa
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?
  1. Almeno $\frac43$ di $z(I)$
  2. Al più $\frac34$ di $z(I)$
  3. Almeno $\frac13$ di $z(I)$
  4. 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.
aa-f-140 · livello teorema · dispensa
Per Ext-Greedy si dimostra $z(I)/GR^e(I)\le2$ e poi che esistono istanze con $z(I)/GR^e(I)\to2$. A che cosa serve la seconda proposizione?
  1. A dimostrare la prima proposizione
  2. A mostrare che il rapporto medio è $2$
  3. A mostrare che $2$ non si può abbassare
  4. A mostrare che Ext-Greedy è ottimo su quelle istanze
Spiegazione. Una garanzia è tight se non si può abbassare; una famiglia di istanze con rapporto che tende a $2$ lo prova.
aa-f-141 · livello teorema · dispensa
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?
  1. $c$: perché $GR$ vale solo $1$
  2. $c/2$: il rapporto di $GR$ non è limitato
  3. $2$: è proprio il caso peggiore di $GR$
  4. $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.
aa-f-142 · livello facile · dispensa
Per l'algoritmo $H^2$ dello zaino vale $z(I)/H^2(I)\le\frac43$. Su un'istanza con $z(I)=120$, quale valore minimo garantisce $H^2$?
  1. $90$
  2. $80$
  3. $60$
  4. $100$
Spiegazione. $H^2\ge\frac34\cdot120=90$. $60$ è la garanzia di Ext-Greedy ($\frac12z$); $80$ userebbe il fattore $\frac23$.
aa-f-143 · livello facile · dispensa
Per l'algoritmo $H^{\ell}$ dello zaino vale $z(I)/H^{\ell}(I)\le\frac{\ell+2}{\ell+1}$ (tight). Quale garanzia dà $\ell=4$?
  1. $\frac54$
  2. $\frac43$
  3. $\frac76$
  4. $\frac65$
Spiegazione. $\frac{4+2}{4+1}=\frac65$. Con $\ell=2$ si ritrova $\frac43$, il rapporto di $H^2$.
aa-f-144 · livello facile · dispensa
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?
  1. $\ell=8$, tempo $O(n^2/\varepsilon)$
  2. $\ell=1$, tempo $O(n^2)$
  3. $\ell=8$, tempo $O(n^9)$
  4. $\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.
aa-f-145 · livello teorema · dispensa
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?
  1. Aumentare la capacità di $k$
  2. Moltiplicare i profitti per $k+1$
  3. Dividere i profitti per $k$ e arrotondare
  4. 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.
aa-f-146 · livello facile · dispensa
Lo zaino 0/1 è NP-difficile. Se $P\neq NP$, quale tipo di garanzia ammette in tempo polinomiale?
  1. Solo relativa, fino a un FPTAS
  2. Solo assoluta, con errore costante $k$
  3. Entrambe, relativa e assoluta
  4. 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)

aa-f-009 · livello teorema · dispensa
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)$?
  1. $r(NF)=r(WF)=2$ e $r(FF)=r(BF)=\frac{17}{10}$
  2. $r(NF)=2$ e $r(WF)=r(FF)=r(BF)=\frac{17}{10}$
  3. $r(NF)=r(WF)=r(FF)=r(BF)=2$
  4. $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}$.
aa-f-010 · livello ipotesi · dispensa
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?
  1. 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
  2. Ogni oggetto pesa più di $c/2$; ogni soluzione con $z(I)$ contenitori ha $\sum_i w_i\le z(I)\,c$; $k$ è intero
  3. Gli oggetti sono ordinati per peso non crescente; $z(I)\ge\lceil\sum_i w_i/c\rceil$; $k$ è intero
  4. 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)$.
aa-f-011 · livello ipotesi · dispensa
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$)?
  1. Gli oggetti sono ordinati per peso non crescente, quindi i primi contenitori sono pieni
  2. Il numero di contenitori è al più $\frac{17}{10}z(I)$, quindi pochi contenitori sono vuoti
  3. Il contenuto di due contenitori non sta mai in uno solo, qualunque sia la regola di scelta del contenitore
  4. 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$.
aa-f-012 · livello facile · dispensa
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?
  1. Può superare la capacità del contenitore aperto
  2. Può aprire un contenitore per un oggetto che entrerebbe in un contenitore chiuso
  3. Ordina gli oggetti per peso non crescente prima di sistemarli
  4. 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.
aa-f-048 · livello facile · dispensa
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?
  1. NF $4$, FF $2$
  2. NF $3$, FF $2$
  3. NF $2$, FF $2$
  4. 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.
aa-f-049 · livello facile · dispensa
Nel bin packing con $n$ oggetti, Next Fit (NF) tiene aperto un solo contenitore alla volta. Quanto tempo richiede, e perché?
  1. $O(n)$: ogni oggetto si confronta solo con il contenitore aperto
  2. $O(n^2)$: ogni oggetto si confronta con tutti i contenitori
  3. $O(n\log n)$: gli oggetti vanno ordinati
  4. $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.
aa-f-050 · livello facile · dispensa
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)?
  1. FF nel primo, BF nel primo, WF nel secondo
  2. FF nel terzo, BF nel terzo, WF nel secondo
  3. FF nel secondo, BF nel secondo, WF nel terzo
  4. 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.
aa-f-051 · livello facile · dispensa
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)?
  1. Sì, ma solo con Worst Fit
  2. No, perché il carico totale $15$ non è multiplo di $c$
  3. No: due contenitori hanno carico al più $5$, e il contenuto del secondo sarebbe entrato nel primo
  4. 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à.
aa-f-052 · livello ipotesi · dispensa
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?
  1. Il contenuto di due contenitori qualsiasi non sta in uno solo
  2. Due contenitori consecutivi di NF hanno insieme peso maggiore di $c$
  3. Ogni contenitore di NF ha peso maggiore di $c/2$
  4. 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$.
aa-f-053 · livello facile · dispensa
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?
  1. $5$
  2. $6$
  3. $4$
  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)$.
aa-f-054 · livello facile · dispensa
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}$?
  1. Worst Fit non è un algoritmo Any Fit
  2. First Fit e Best Fit violano la proprietà half-full
  3. Le garanzie dipendono solo dall'ordine degli oggetti
  4. 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.
aa-f-055 · livello facile · dispensa
Next Fit (NF) per il bin packing ha rapporto nel caso peggiore $r(NF)=2$. Quale tipo di istanza lo avvicina?
  1. Oggetti ordinati per peso non crescente
  2. Oggetti tutti di peso $1$, con $c$ grande
  3. Oggetti che alternano peso circa $c/2$ e peso molto piccolo: NF chiude ogni contenitore mezzo vuoto
  4. 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.
aa-f-104 · livello facile · dispensa
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?
  1. $\mathscr{A}(I)/z(I)\le1$
  2. $\mathscr{A}(I)/z(I)\ge1$
  3. $z(I)/\mathscr{A}(I)\ge1$
  4. $\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.
aa-f-105 · livello facile · dispensa
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é?
  1. Next Fit: chiude il contenitore appena un oggetto non vi entra, anche se l'oggetto entrerebbe in uno precedente
  2. First Fit: sceglie il primo contenitore
  3. Best Fit: sceglie il contenitore più pieno
  4. 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.
aa-f-106 · livello teorema · dispensa
In una soluzione prodotta da un algoritmo Any Fit per il bin packing, due contenitori qualsiasi hanno insieme peso maggiore di $c$. Perché?
  1. Perché ogni contenitore è pieno oltre metà per costruzione della regola di scelta
  2. Perché gli oggetti sono ordinati per peso
  3. Non è vero per Worst Fit
  4. 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.
aa-f-107 · livello facile · dispensa
Bin packing con $c=10$ e oggetti, nell'ordine, di peso $(6,5,4,3)$. Quanti contenitori usa First Fit e con quali carichi?
  1. $2$, con carichi $(9,9)$
  2. $4$, con carichi $(6,5,4,3)$
  3. $2$, con carichi $(10,8)$
  4. $3$, con carichi $(6,9,3)$
Spiegazione. $6$ apre il contenitore $1$; $5$ non entra ($11$) e apre il $2$; $4$ entra nel $1$ ($10$); $3$ non entra nel $1$ ed entra nel $2$ ($8$).
aa-f-108 · livello facile · dispensa
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)?
  1. In un contenitore nuovo
  2. Nel contenitore $2$, che diventa pieno
  3. Nel contenitore $1$, il primo in cui entra
  4. 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$.
aa-f-109 · livello facile · dispensa
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?
  1. Rapporto $2$, stretto; First Fit ha rapporto asintotico $\frac{17}{10}$
  2. Rapporto $\frac{17}{10}$, come First Fit
  3. Rapporto $\frac32$
  4. 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}$.
aa-f-110 · livello teorema · dispensa
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)$?
  1. Che nessun algoritmo Any Fit ha rapporto minore di $2$
  2. Che Worst Fit non è Any Fit
  3. Che First Fit ha rapporto $2$
  4. 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}$.
aa-f-111 · livello facile · dispensa
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?
  1. $200$
  2. $150$
  3. $170$
  4. $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.
aa-f-112 · livello ipotesi · dispensa
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?
  1. Next Fit ha garanzia $\frac{17}{10}$
  2. Next Fit mantiene comunque $NF(I)\le2z(I)$, perché due contenitori consecutivi superano insieme $c$
  3. Next Fit perde ogni garanzia costante
  4. 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.
aa-f-152 · livello facile · dispensa
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. $(1,2,2,3,4,5)$
  2. $(1,2,2,3,4,4)$
  3. $(1,2,1,3,4,1)$
  4. $(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.
aa-f-153 · livello facile · dispensa
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?
  1. $P_3=\{4,5,6\}$, peso $8$
  2. $P_3=\{3\}$, peso $8$
  3. $P_3=\{3,4,5\}$, peso $14$
  4. $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$.
aa-f-154 · livello facile · dispensa
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$?
  1. Apre un nuovo contenitore e ve lo mette
  2. Lo mette nel primo contenitore chiuso in cui entra
  3. Lo scarta e passa all'oggetto successivo
  4. 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.
aa-f-155 · livello facile · dispensa
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?
  1. $4$, con carichi $(5,10,6,6)$
  2. $4$, con carichi $(10,7,4,6)$
  3. $3$, con carichi $(10,7,10)$
  4. $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$.
aa-f-156 · livello facile · dispensa
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?
  1. Sempre l'ultimo contenitore aperto finora
  2. Il primo contenitore (in ordine di apertura) in cui entra
  3. L'ordine degli oggetti, esaminati per peso non crescente
  4. 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.
aa-f-157 · livello facile · dispensa
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. $(1,2,2,1,3)$
  2. $(1,2,1,2,3)$
  3. $(1,2,2,3,3)$
  4. $(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.
aa-f-158 · livello facile · dispensa
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?
  1. Nel contenitore $2$
  2. Nel contenitore $3$
  3. Nel contenitore $4$
  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.
aa-f-159 · livello facile · dispensa
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?
  1. Entrambi $2$
  2. Entrambi $3$
  3. FF $3$, WF $2$
  4. 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.
aa-f-160 · livello facile · dispensa
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?
  1. Esaminare per primi gli oggetti più pesanti
  2. Non lasciare residui troppo piccoli per gli oggetti futuri
  3. Riempire il più possibile ogni contenitore aperto
  4. 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.
aa-f-161 · livello facile · dispensa
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à?
  1. $6$, e non la ha: tre contenitori hanno carico $2$
  2. $6$, e la ha: due contenitori consecutivi superano $10$
  3. $4$, e la ha: un solo contenitore ha carico $\le5$
  4. $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)$.
aa-f-162 · livello facile · dispensa
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?
  1. Per ogni coppia di contenitori, insieme pesano più di $c$
  2. Ogni contenitore, senza eccezioni, pesa più di $c/2$
  3. Al più un contenitore non è riempito del tutto
  4. 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.
aa-f-163 · livello facile · dispensa
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?
  1. No, non la ha; e sì, si possono fondere
  2. No, non la ha; e non si possono fondere
  3. Sì, la ha; e sì, si possono fondere
  4. 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$.
aa-f-164 · livello teorema · dispensa
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)$?
  1. Da $\sum_iw_i\le c$, che vale per ogni istanza
  2. Da $k-1<2z(I)$, perché $k$ e $z(I)$ sono interi
  3. Da $k<2z(I)$, dividendo per $\frac c2$
  4. 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)$.
aa-f-165 · livello ipotesi · dispensa
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à?
  1. Sì: la dimostrazione usa solo la proprietà della soluzione
  2. No: la dimostrazione usa la condizione Any Fit
  3. Sì, ma solo nel limite $z(I)\to\infty$
  4. 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à.
aa-f-166 · livello facile · dispensa
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?
  1. $NF=10$, $z=5$, rapporto $2$
  2. $NF=20$, $z=6$, rapporto $\frac{10}3$
  3. $NF=10$, $z=10$, rapporto $1$
  4. $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$.
aa-f-167 · livello facile · dispensa
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)$?
  1. $7$
  2. $2$
  3. $4$
  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$.
aa-f-168 · livello teorema · dispensa
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?
  1. Perché gli oggetti piccoli finiscono tutti nel primo contenitore aperto
  2. Ogni oggetto piccolo va nel contenitore nuovo, che resta con residuo $\frac n2-2$
  3. Perché due oggetti di peso $\frac n2$ insieme superano la capacità $c=n$
  4. 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.
aa-f-169 · livello facile · dispensa
Nel bin packing Next Fit e Worst Fit hanno lo stesso rapporto nel caso peggiore, $r(NF)=r(WF)=2$. Sono quindi equivalenti?
  1. No: solo NF può lasciare molti contenitori pieni a metà o meno
  2. Sì: lo stesso rapporto vuol dire le stesse soluzioni
  3. No: WF usa sempre meno contenitori di NF, su ogni istanza
  4. 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.
aa-f-170 · livello facile · dispensa
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?
  1. Il fattore è sceso da $2$ a $\frac{17}{10}$
  2. Il risultato vale ora anche per Worst Fit
  3. Il risultato vale ora solo con oggetti ordinati
  4. È 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$.
aa-f-171 · livello teorema · dispensa
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?
  1. È al più $\frac{17}{10}$, come First Fit
  2. Nulla: la condizione Any Fit non dà garanzie
  3. È compreso fra $\frac{17}{10}$ e $2$
  4. È 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.
aa-f-172 · livello facile · dispensa
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$?
  1. La costante additiva $+2$ del bound di First Fit
  2. La regola con cui si sceglie fra i contenitori in cui l'oggetto entra
  3. L'ordine in cui gli oggetti vengono esaminati
  4. 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)

aa-f-013 · livello teorema · dispensa
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?
  1. Ha una $(\Delta(G)+1)$-approssimazione per ogni grafo, $DSATUR$
  2. Non ha $\alpha$-approssimazioni polinomiali per nessuna costante $\alpha\ge 1$
  3. Ha una $\frac43$-approssimazione polinomiale, ma nessuna sotto $\frac43$
  4. 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)$.
aa-f-014 · livello ipotesi · dispensa
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:
  1. che decidere se $\chi(G)\le 3$ è NP-completo, e che il numero di colori è intero
  2. che decidere se $\chi(G)\le 2$ è NP-completo, e che il numero di colori è intero
  3. che decidere se $\chi(G)\le 4$ è NP-completo, e che i grafi planari hanno $\chi(G)\le 4$
  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.
aa-f-015 · livello facile · dispensa
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?
  1. Per estremo destro $b_v$ non crescente
  2. Per lunghezza $b_v-a_v$ non crescente
  3. Con qualsiasi ordine dei vertici
  4. 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.
aa-f-016 · livello facile · dispensa
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?
  1. $O(2^n)$: il problema è NP-completo
  2. $O(nm)$, con un cammino minimo da ogni vertice
  3. $O(n+m)$, con una visita in ampiezza
  4. $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.
aa-f-056 · livello ipotesi · dispensa
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$?
  1. Userebbe $2$ colori, contraddicendo $\chi(G)=3$
  2. Non terminerebbe, perché il problema è NP-difficile
  3. Userebbe meno di $4$ colori, cioè $3$: deciderebbe in tempo polinomiale se $\chi(G)\le 3$
  4. 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$.
aa-f-057 · livello facile · dispensa
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é?
  1. Perché con $2$ colori la colorazione greedy è sempre ottima
  2. Decidere se $\chi(G)\le 2$ è polinomiale (grafi bipartiti), quindi non si ottiene nessuna contraddizione
  3. Perché nessun grafo ha $\chi(G)=2$
  4. 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)$.
aa-f-058 · livello facile · dispensa
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$)?
  1. Rapporto al più $n$; nessun algoritmo polinomiale garantisce $n^{1-\varepsilon}$ per nessun $\varepsilon>0$
  2. Rapporto al più $2$; nessun algoritmo polinomiale garantisce meno di $2$
  3. Rapporto al più $\Delta+1$; nessun algoritmo polinomiale garantisce meno di $\frac43$
  4. 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.
aa-f-059 · livello facile · dispensa
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?
  1. $30$
  2. $45$
  3. $27$
  4. $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.
aa-f-060 · livello facile · dispensa
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?
  1. Nessuna: i grafi planari sono difficili come tutti gli altri
  2. Additiva: $PL(I)-\chi(G)\le 0$, cioè $PL$ è esatto
  3. Additiva: $PL(I)-\chi(G)\le 2$, riconoscendo a parte i grafi con $\chi(G)\le 2$
  4. 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$.
aa-f-061 · livello facile · dispensa
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?
  1. Esattamente $1$: su questi grafi è ottima
  2. Al più $2$, perché usa al più $4$ colori e $\chi(G)\ge 2$
  3. Al più $4$, perché usa al più $4$ colori e $\chi(G)\ge 1$
  4. 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.
aa-f-062 · livello facile · dispensa
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?
  1. $3$
  2. $4$
  3. $2$
  4. $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)$.
aa-f-063 · livello facile · dispensa
Il teorema di Zuckerman esclude, se $P\neq NP$, i rapporti $n^{1-\varepsilon}$ per la colorazione. Perché esclude anche ogni rapporto costante $\alpha$?
  1. Perché ogni costante è minore di $\frac43$
  2. Perché i rapporti costanti valgono solo sui grafi planari
  3. Non lo esclude: esistono $\alpha$-approssimazioni con $\alpha$ grande
  4. 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.
aa-f-113 · livello facile · dispensa
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?
  1. $\omega(G)/\mathscr{A}(I)$
  2. $\mathscr{A}(I)/\chi(G)\ge1$
  3. $\chi(G)/\mathscr{A}(I)\ge1$
  4. $\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.
aa-f-114 · livello facile · dispensa
Il grafo di Petersen ha $n=10$, $m=15$, grado massimo $\Delta=3$ e contiene cicli di lunghezza $5$. Quali conseguenze ha per la colorazione?
  1. Non è bipartito, quindi $\chi\ge3$; il bound $\Delta+1$ dà $\chi\le4$
  2. È bipartito, quindi $\chi=2$
  3. $\chi=\Delta+1=4$ sempre
  4. $\chi=n/2=5$
Spiegazione. Un ciclo dispari impedisce la $2$-colorazione; la colorazione greedy garantisce al più $\Delta+1=4$ colori. In realtà $\chi=3$.
aa-f-123 · livello facile · dispensa
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?
  1. I grafi completi: servono $2$ colori
  2. I grafi con un triangolo: bastano $3$ colori
  3. Tutti i grafi con $n\le100$
  4. 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.
aa-f-173 · livello facile · dispensa
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?
  1. Esatta su grado limitato e intervalli; garanzia su bipartiti e planari
  2. Esatta su bipartiti e intervalli; garanzia su grado limitato e planari
  3. Esatta su tutte e quattro le classi
  4. 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.
aa-f-174 · livello facile · dispensa
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?
  1. Il teorema parla di tutti i grafi; i difficili non sono bipartiti
  2. Perché sui grafi bipartiti il numero cromatico è $\chi(G)=1$
  3. Perché il teorema vale solo nell'ipotesi $P=NP$
  4. 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$.
aa-f-175 · livello facile · dispensa
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?
  1. $\{4,6\}$: un cammino chiuso di lunghezza $6$, quindi $\chi\ge3$
  2. Nessuno: il grafo è bipartito e $\chi=2$
  3. $\{5,6\}$: un cammino chiuso di lunghezza $4$, quindi $\chi\ge3$
  4. $\{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.
aa-f-176 · livello facile · dispensa
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?
  1. Esattamente $3$
  2. Dipende dal grado massimo $\Delta(G)$
  3. Esattamente $2$
  4. $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.
aa-f-177 · livello facile · dispensa
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$?
  1. $2$ colori con ogni ordine; $\Delta+1=9$
  2. $2$ colori con ogni ordine; $\Delta+1=10$
  3. $10$ colori con ogni ordine; $\Delta+1=10$
  4. 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$.
aa-f-178 · livello teorema · dispensa
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?
  1. Grafi completi e cicli dispari; per gli altri $\chi(G)\le\Delta(G)$
  2. Alberi e cicli pari; per gli altri $\chi(G)\le\Delta(G)-1$
  3. Grafi planari; per gli altri $\chi(G)\le4$
  4. 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.
aa-f-179 · livello teorema · dispensa
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$?
  1. Sui planari esiste un algoritmo esatto, ma non polinomiale in $n$
  2. L'errore additivo minimo possibile sui planari è $2$
  3. Sui planari nessun algoritmo ha rapporto costante
  4. 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$.
aa-f-180 · livello ipotesi · dispensa
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$?
  1. Perché così il grafo $G-v$ diventa bipartito
  2. Perché ogni grafo planare ha grado massimo al più $5$
  3. I vicini usano al più $5$ colori; se tutti, uno scambio ne libera uno
  4. 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).
aa-f-181 · livello facile · dispensa
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?
  1. Per numero di intersezioni (grado) non crescente
  2. Per estremo sinistro $a_v$ non decrescente
  3. In qualunque ordine: sui grafi di intervalli è sempre ottima
  4. 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ù.
aa-f-182 · livello facile · dispensa
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?
  1. L'ottimalità è garantita solo con l'ordine per estremo sinistro
  2. Il numero cromatico di questo grafo è $\chi(G)=4$
  3. Il grafo dato non è un grafo di intervalli
  4. 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$).
aa-f-230 · livello facile · dispensa
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$)?
  1. Decidere se $\chi(G)\le3$
  2. Decidere se $\chi(G)\le2$
  3. Decidere se $G$ è planare
  4. 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à.
aa-f-231 · livello facile · dispensa
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. $1+\varepsilon$
  2. $\log n$
  3. $\frac43-\varepsilon$
  4. $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}$.
aa-f-232 · livello facile · dispensa
Quando un grafo $G=(V,E)$ si dice bipartito?
  1. Se $\omega(G)=2$
  2. Se ogni vertice ha grado $2$
  3. Se $\chi(G)\le2$
  4. Se ha un numero pari di vertici
Spiegazione. Bipartito vuol dire colorabile con due colori: le due classi di colore sono insiemi stabili.
aa-f-233 · livello facile · dispensa
Con quale complessità si decide se $\chi(G)\le2$ (e si trova una $2$-colorazione se esiste)?
  1. Non si sa in tempo polinomiale
  2. $O(n+m)$, con una visita in ampiezza
  3. $O(2^n)$, provando tutte le partizioni
  4. $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.
aa-f-234 · livello facile · dispensa
Un grafo ha grado massimo $\Delta(G)=5$. Quanti colori usa al più la colorazione greedy, con qualunque ordine dei vertici?
  1. $6$
  2. $5$
  3. $10$
  4. Dipende dall'ordine, senza limite
Spiegazione. Quando il greedy colora un vertice, i suoi vicini già colorati sono al più $\Delta(G)$: uno dei colori $1,\dots,\Delta(G)+1$ è libero.
aa-f-235 · livello facile · dispensa
Quanti spigoli può avere al più un grafo planare semplice con $n=10$ vertici?
  1. $27$
  2. $30$
  3. $45$
  4. $24$
Spiegazione. Per $n\ge3$ un grafo planare ha $m\le3n-6=24$; $45=\binom{10}{2}$ è il grafo completo, che non è planare.
aa-f-236 · livello facile · dispensa
Perché ogni grafo planare ha un vertice di grado al più $5$?
  1. Perché $\omega(G)\le4$ in ogni grafo planare
  2. Perché ogni faccia del disegno è un triangolo
  3. Perché $m\le3n-6$: la somma dei gradi $2m$ è minore di $6n$
  4. Perché i grafi planari sono sempre bipartiti
Spiegazione. Se tutti i gradi fossero almeno $6$ si avrebbe $2m\ge6n$, contro $2m\le6n-12$.
aa-f-237 · livello facile · dispensa
Che cosa afferma il teorema di Heawood (1890) sui grafi planari?
  1. Ogni grafo planare è bipartito
  2. Ogni grafo planare si colora con $5$ colori
  3. Ogni grafo planare si colora con $3$ colori
  4. 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.
aa-f-238 · livello facile · dispensa
L'algoritmo $PL$ sui grafi planari restituisce $4$ colori su un grafo con $\chi(G)=3$. È coerente con la garanzia di $PL$?
  1. Sì: l'errore $4-3=1$ è al più $2$
  2. No: $PL$ è esatto sui grafi planari
  3. No: $PL$ usa sempre $5$ colori
  4. Sì, ma solo perché $\chi(G)\ge4$
Spiegazione. $PL$ è $2$-additivo: $PL(I)-\chi(G)\le2$; con $\chi(G)=3$ può restituire $3$, $4$ o $5$ colori.
aa-f-239 · livello facile · dispensa
In un grafo di intervalli, quando due vertici $u$ e $v$ sono adiacenti?
  1. Quando $a_u=a_v$
  2. Quando un intervallo contiene l'altro
  3. Quando gli intervalli sono disgiunti
  4. Quando gli intervalli si intersecano
Spiegazione. La definizione associa a ogni vertice un intervallo chiuso; gli spigoli sono le coppie di intervalli con almeno un punto in comune.
aa-f-240 · livello facile · dispensa
Su un grafo di intervalli, con quale ordine dei vertici la colorazione greedy è ottima?
  1. Per grado decrescente dei vertici
  2. Con qualunque ordine dei vertici
  3. Per estremo sinistro $a_v$ non decrescente
  4. 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.
aa-f-241 · livello facile · dispensa
Su un grafo con $\Delta(G)=3$, il greedy usa al più $4$ colori. Quale rapporto garantisce rispetto a $\chi(G)$, se $G$ ha almeno uno spigolo?
  1. Il greedy è ottimo su questi grafi
  2. Al più $2$, perché $\chi(G)\ge2$
  3. Al più $\frac43$, come per i planari
  4. Al più $4$, e non meglio
Spiegazione. Con uno spigolo $\chi(G)\ge2$, quindi $GC(I)/\chi(G)\le4/2=2$: in generale $\frac{\Delta(G)+1}{2}$.
aa-f-242 · livello teorema · dispensa
Quale conseguenza ha il risultato di Zuckerman per l'approssimazione del VCP (se $P\neq NP$)?
  1. Nessuna $\alpha$-approssimazione costante
  2. Il VCP ha un PTAS ma non un FPTAS
  3. Il VCP ha una $\frac43$-approssimazione polinomiale
  4. 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.
aa-f-243 · livello teorema · dispensa
Che cosa dice il teorema 4.1 per un algoritmo polinomiale $\mathscr{A}$ per il VCP, se $P\neq NP$?
  1. Su ogni grafo $\mathscr{A}(I)/\chi(G)\ge\frac43$
  2. Esiste un grafo con $\mathscr{A}(I)-\chi(G)\ge\frac43$
  3. $\mathscr{A}$ è una $\frac43$-approssimazione
  4. Esiste un grafo con $\mathscr{A}(I)/\chi(G)\ge\frac43$
Spiegazione. È un risultato di caso peggiore: c'è almeno un grafo su cui il rapporto è almeno $\frac43$, non su tutti.
aa-f-244 · livello teorema · dispensa
Quale garanzia ha $PL$ sui grafi planari se l'algoritmo dei cinque colori si sostituisce con quello dei quattro colori?
  1. Diventa esatto
  2. Rapporto al più $\frac43$, non additivo
  3. Errore additivo al più $1$
  4. 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.
aa-f-245 · livello teorema · dispensa
Quale disuguaglianza vale, per ogni grafo $G$ e ogni ordine dei vertici, per la colorazione greedy $GC$?
  1. $GC(I)\le\Delta(G)$
  2. $GC(I)\le\Delta(G)+1$
  3. $GC(I)\le\omega(G)$
  4. $GC(I)\le\chi(G)+1$
Spiegazione. Ogni vertice ha al più $\Delta(G)$ vicini colorati prima di lui; $GC(I)\le\Delta(G)$ fallisce sul grafo completo $K_n$.
aa-f-246 · livello teorema · dispensa
Che cosa vale su un grafo di intervalli per la colorazione greedy con i vertici per $a_v$ non decrescente?
  1. $GC(I)=\omega(G)=\chi(G)$
  2. $GC(I)=\Delta(G)+1$
  3. $GC(I)\le2\chi(G)$
  4. $GC(I)=\chi(G)+1$
Spiegazione. Il greedy usa $\omega(G)$ colori e $\omega(G)\le\chi(G)\le GC(I)$: tutte uguali, la colorazione è ottima.
aa-f-247 · livello teorema · dispensa
Che cosa garantisce la visita in ampiezza sui grafi bipartiti?
  1. Una colorazione con al più $3$ colori
  2. Una $\frac43$-approssimazione
  3. Il numero di clique $\omega(G)$
  4. Una colorazione ottima
Spiegazione. Sui bipartiti la visita trova una $2$-colorazione, ottima perché un grafo con uno spigolo richiede $2$ colori.
aa-f-248 · livello teorema · dispensa
Su quale proprietà dei grafi planari si basa l'algoritmo polinomiale dei cinque colori?
  1. Ogni grafo planare ha $\omega(G)\le3$
  2. Ogni grafo planare è un grafo di intervalli
  3. Ogni grafo planare ha un vertice di grado al più $5$
  4. Ogni grafo planare è un grafo bipartito
Spiegazione. Si toglie un vertice di grado $\le5$, si colora il resto e lo si reinserisce, ricolorando se i suoi vicini usano tutti e cinque i colori.
aa-f-249 · livello ipotesi · dispensa
Il teorema 4.1 (nessun rapporto sempre $<\frac43$) richiede quale ipotesi?
  1. Che $\chi(G)\ge4$
  2. $P\neq NP$
  3. Che il grafo sia planare
  4. Che l'algoritmo sia greedy
Spiegazione. Se $P=NP$ la $3$-colorabilità sarebbe decidibile in tempo polinomiale e la dimostrazione cadrebbe.
aa-f-250 · livello ipotesi · dispensa
Il teorema 4.1 riguarda gli algoritmi per il VCP con quale proprietà?
  1. Algoritmi polinomiali
  2. Algoritmi esatti
  3. Algoritmi con garanzia additiva
  4. Algoritmi greedy
Spiegazione. Un algoritmo esponenziale può trovare $\chi(G)$ esattamente: il limite vale per gli algoritmi polinomiali.
aa-f-251 · livello ipotesi · dispensa
Il lemma $m\le3n-6$ sui grafi planari vale sotto quale ipotesi sul numero di vertici?
  1. $n\ge1$
  2. $n$ pari
  3. $n\ge6$
  4. $n\ge3$
Spiegazione. Con $n=2$ e uno spigolo si avrebbe $1\le0$: il lemma richiede almeno tre vertici.
aa-f-252 · livello ipotesi · dispensa
La garanzia $PL(I)-\chi(G)\le2$ vale per quali grafi?
  1. Per i grafi con $\Delta(G)\le5$
  2. Per i grafi di intervalli
  3. Per i grafi planari
  4. Per tutti i grafi
Spiegazione. $PL$ usa l'algoritmo dei cinque colori, che funziona solo sui grafi planari; sui grafi generali nessuna garanzia costante.
aa-f-253 · livello ipotesi · dispensa
Nell'analisi di $PL$, perché sui grafi planari non bipartiti l'errore è al più $2$?
  1. Perché i grafi planari hanno $\omega(G)\le2$ e $\Delta(G)\le5$
  2. Perché $\chi(G)\ge3$ e $PL$ usa $\le5$ colori
  3. Perché i grafi planari hanno sempre $\chi(G)\le2$
  4. Perché $PL$ colora ogni grafo con la visita in ampiezza
Spiegazione. I grafi bipartiti si colorano all'ottimo; sugli altri $\chi(G)\ge3$ e i colori sono al più $5$: $5-3=2$.
aa-f-254 · livello ipotesi · dispensa
La colorazione greedy è ottima sui grafi di intervalli: quale ipotesi sull'ordine dei vertici serve?
  1. L'ordine per estremo sinistro non decrescente
  2. Nessuna: ogni ordine dei vertici è ottimo
  3. L'ordine per lunghezza dell'intervallo
  4. L'ordine per grado crescente dei vertici
Spiegazione. Con un ordine qualunque il greedy può usare più di $\omega(G)$ colori anche su un grafo di intervalli.
aa-f-255 · livello ipotesi · dispensa
Il risultato di Zuckerman sul VCP vale per quali $\varepsilon$?
  1. Solo per $\varepsilon\ge\frac12$
  2. Solo per $\varepsilon<\frac13$
  3. Per $\varepsilon=0$
  4. Per ogni $\varepsilon>0$
Spiegazione. Per ogni $\varepsilon>0$, se $P\neq NP$: con $\varepsilon=0$ il rapporto $n$ è banalmente raggiungibile.
aa-f-256 · livello ipotesi · dispensa
Il bound $GC(I)\le\Delta(G)+1$ dipende dall'ordine in cui il greedy colora i vertici?
  1. Sì: solo per l'ordine dei nomi
  2. Sì: solo sui grafi planari
  3. No: vale per ogni ordine
  4. Sì: solo per grado decrescente
Spiegazione. La dimostrazione usa solo che un vertice ha al più $\Delta(G)$ vicini: vale qualunque sia l'ordine.
aa-f-324 · livello teorema · dispensa
Su un grafo di intervalli, quanto vale $\omega(G)$?
  1. Il grado massimo del grafo più uno
  2. Il numero di intervalli a due a due disgiunti
  3. Il massimo di intervalli con un punto comune
  4. 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.
aa-f-325 · livello teorema · dispensa
Nella dimostrazione del bound $\frac43$, che cosa farebbe un algoritmo con rapporto sempre $<\frac43$ su un grafo con $\chi(G)=3$?
  1. Non terminerebbe
  2. Userebbe al più $3$ colori
  3. Userebbe almeno $4$ colori
  4. Userebbe $2$ colori
Spiegazione. $\mathscr{A}(I)<\frac43\cdot3=4$, quindi $\mathscr{A}(I)\le3$: così si deciderebbe la $3$-colorabilità.
aa-f-326 · livello teorema · dispensa
Il VCP ha uno schema di approssimazione (PTAS), se $P\neq NP$?
  1. No: nemmeno un rapporto costante
  2. Sì, un PTAS ma non un FPTAS
  3. Sì, ha anche un FPTAS
  4. Sì, sui grafi generali
Spiegazione. Un PTAS darebbe un rapporto $1+\varepsilon$ costante, escluso dal corollario.
aa-f-327 · livello ipotesi · dispensa
Il corollario «niente rapporto costante per il VCP» vale per quali grafi?
  1. Per i grafi planari
  2. Per i grafi di intervalli
  3. Per i grafi bipartiti
  4. Per i grafi generali
Spiegazione. Sui planari $PL$ è $2$-additivo e sugli intervalli e i bipartiti si colora all'ottimo: il limite riguarda i grafi qualunque.
aa-f-328 · livello ipotesi · dispensa
L'algoritmo dei cinque colori si applica sotto quale ipotesi?
  1. Che $\omega(G)\le5$
  2. Che il grafo sia di intervalli
  3. Che il grafo sia planare
  4. Che $\Delta(G)\le5$
Spiegazione. Usa il vertice di grado al più $5$, che esiste in ogni grafo planare ma non in un grafo qualunque.
aa-f-329 · livello ipotesi · dispensa
La visita in ampiezza colora all'ottimo con $2$ colori: sotto quale ipotesi?
  1. Che $\Delta(G)\le2$
  2. Che il grafo sia bipartito
  3. Che il grafo sia planare
  4. Che il grafo sia connesso e completo
Spiegazione. Se il grafo non è bipartito la visita trova uno spigolo fra vertici dello stesso colore e $\chi(G)\ge3$.
aa-f-356 · livello teorema · dispensa
Che cosa fa l'algoritmo $PL$ su un grafo planare?
  1. Usa il greedy per grado
  2. Prova tutte le colorazioni
  3. Ottimo sui bipartiti, se no $5$
  4. Usa sempre $4$ colori
Spiegazione. Prima la visita in ampiezza (bipartito?), altrimenti l'algoritmo dei cinque colori: errore al più $2$.

5. Clique massima: limiti dell'approssimazione (56)

aa-f-017 · livello teorema · dispensa
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?
  1. $\omega(G\boxtimes H)=\omega(G)+\omega(H)$
  2. $\omega(G\boxtimes H)=\max\{\omega(G),\omega(H)\}$
  3. $\omega(G\boxtimes H)=\omega(G)^{\omega(H)}$
  4. $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$
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.
aa-f-018 · livello ipotesi · dispensa
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:
  1. $\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
  2. $\omega(G)=\alpha(\overline{G})$; da un insieme stabile di $\overline{G}$ si estrae una clique di $G$; la proprietà half-full
  3. $\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
  4. $\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.
aa-f-019 · livello facile · dispensa
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?
  1. $\omega(G)\le 5$ e l'MCP si risolve in $O(n^5)$, mentre l'MSSP resta NP-difficile
  2. $\omega(G)\le 4$ e l'MCP si risolve in $O(n^4)$, mentre l'MSSP resta NP-difficile
  3. $\omega(G)\le 4$ e l'MCP si risolve in $O(n^4)$; anche l'MSSP, passando al complementare
  4. $\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.
aa-f-020 · livello facile · dispensa
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?
  1. $4$
  2. $5$
  3. $6$
  4. $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.
aa-f-064 · livello facile · dispensa
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$?
  1. $25$ vertici, $\omega(G\boxtimes G)=4$
  2. $10$ vertici, $\omega(G\boxtimes G)=4$
  3. $25$ vertici, $\omega(G\boxtimes G)=2$
  4. $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.
aa-f-065 · livello facile · dispensa
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?
  1. $8$
  2. $16$
  3. $2$
  4. $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.
aa-f-066 · livello facile · dispensa
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$?
  1. $16$
  2. $\frac43$
  3. $2$
  4. $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$.
aa-f-067 · livello facile · dispensa
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$)?
  1. Al più $\sqrt n$; esiste un PTAS
  2. Al più $n$; nessun algoritmo polinomiale garantisce $n^{1-\varepsilon}$ per nessun $\varepsilon>0$
  3. Al più $2$; nessun algoritmo polinomiale garantisce meno di $2$
  4. 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.
aa-f-068 · livello facile · dispensa
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$?
  1. Per ogni $\Delta$ fissato, e anche quando $\Delta\le\log_2 n$
  2. Solo per $\Delta\le 3$
  3. Mai: $2^{\Delta}$ è sempre esponenziale
  4. 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.
aa-f-069 · livello facile · dispensa
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$?
  1. Al più $3$
  2. Al più $\frac43$
  3. Nessun rapporto costante
  4. 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.
aa-f-070 · livello facile · dispensa
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?
  1. Perché il complementare di un grafo planare è ancora planare
  2. Perché sui grafi planari $\alpha(G)=\omega(G)$
  3. Il complementare di un grafo planare o di grado limitato è denso: sulla classe originale l'insieme stabile resta NP-difficile
  4. 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).
aa-f-071 · livello facile · dispensa
Nel problema della clique massima su un grafo planare con $n$ vertici, perché basta esaminare i sottoinsiemi di al più $4$ vertici?
  1. Perché i grafi planari hanno al più $4n$ lati
  2. Ogni grafo planare ha $\omega(G)\le 4$ ($K_5$ non è planare): si controllano $O(n^4)$ sottoinsiemi
  3. Perché ogni grafo planare ha grado massimo al più $4$
  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.
aa-f-115 · livello facile · dispensa
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?
  1. $\mathscr{A}(I)=\omega(G)$
  2. $\mathscr{A}(I)\le\omega(G)$ e $\omega(G)/\mathscr{A}(I)\ge1$
  3. $\mathscr{A}(I)\ge\omega(G)$
  4. $\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$.
aa-f-116 · livello facile · dispensa
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?
  1. $9$, da $\{1,2,3\}\times\{1,2,3\}$
  2. $6$, da $\{1,2,3\}\times\{1,2\}$
  3. $3$, da $\{1,2,3\}\times\{1\}$
  4. $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.
aa-f-183 · livello facile · dispensa
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$?
  1. $t=2$, su un grafo con $2n^2$ vertici
  2. $t=2$, su un grafo con $n^4$ vertici
  3. $t=1$, su un grafo con $n^2$ vertici
  4. $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.
aa-f-184 · livello facile · dispensa
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?
  1. L'ipotesi: $NP\neq ZPP$ per Håstad, $P\neq NP$ per Zuckerman
  2. Il limite: $n^{1/2}$ per Håstad, $n^{1-\varepsilon}$ per Zuckerman
  3. Il problema: clique per Håstad, insieme stabile per Zuckerman
  4. 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$.
aa-f-185 · livello teorema · dispensa
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?
  1. Il problema ha un PTAS ma non un FPTAS
  2. Il problema ha rapporto $2$ ma non un PTAS
  3. Il problema ha rapporto $n^{1/2}$ ma non costante
  4. 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).
aa-f-186 · livello facile · dispensa
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?
  1. $K_5$ ha $5$ vertici di grado $4$, più di $3$
  2. $K_5$ ha più di $3\cdot5=15$ spigoli
  3. $K_5$ ha $10$ spigoli, più di $3\cdot5-6=9$
  4. $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$.
aa-f-187 · livello facile · dispensa
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$?
  1. Per ogni grafo con $\Delta\le\sqrt n$
  2. Per $\Delta$ fissato, e anche per $\Delta\le\log_2n$
  3. Solo per grafi con $\Delta\le3$, come i cubici
  4. 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.
aa-f-188 · livello facile · dispensa
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?
  1. $28$
  2. $64$
  3. $12$
  4. $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.
aa-f-189 · livello facile · dispensa
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?
  1. La fibra $\{4,5\}$: ha $2\ge\sqrt6$ vertici
  2. $K$ stessa: è già una clique di $G$
  3. $\{1,2,3,4,5\}$: unisce proiezione e fibra
  4. $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$.
aa-f-257 · livello facile · dispensa
Nel prodotto forte $G\boxtimes H$, quando due vertici distinti $(u,x)$ e $(v,y)$ sono adiacenti?
  1. Se $\{u,v\}\in E$ e anche $\{x,y\}\in F$, senza altri casi
  2. Se $u=v$ oppure $x=y$, qualunque siano gli spigoli
  3. Se $\{u,v\}\in E$ oppure $\{x,y\}\in F$, anche da soli
  4. 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».
aa-f-258 · livello facile · dispensa
Quanti vertici ha il prodotto forte di un grafo con $5$ vertici e di un grafo con $7$ vertici?
  1. $5^7$
  2. $70$
  3. $35$
  4. $12$
Spiegazione. L'insieme dei vertici è il prodotto cartesiano $V\times W$: $5\cdot7=35$ vertici.
aa-f-259 · livello facile · dispensa
Se $\omega(G)=3$ e $\omega(H)=4$, quanto vale $\omega(G\boxtimes H)$?
  1. $81$
  2. $12$
  3. $7$
  4. $4$
Spiegazione. Per la proposizione 5.2 il numero di clique del prodotto forte è il prodotto dei numeri di clique: $3\cdot4=12$.
aa-f-260 · livello facile · dispensa
Se $K$ è una clique di $G\boxtimes H$, che cosa è la sua proiezione $p(K)$ sui vertici di $G$?
  1. Una clique di $G$
  2. Un insieme stabile di $G$
  3. Una clique di $H$
  4. Un insieme qualunque di vertici di $G$
Spiegazione. Due elementi di $K$ con prime coordinate diverse hanno prime coordinate adiacenti in $G$: la proiezione è una clique.
aa-f-261 · livello facile · dispensa
La potenza forte $G^{\boxtimes k}$ di un grafo con $n$ vertici: quanti vertici ha e quanto vale il suo numero di clique?
  1. $kn$ vertici e $k\,\omega(G)$
  2. $n^k$ vertici e $k\,\omega(G)$
  3. $kn$ vertici e $\omega(G)^k$
  4. $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.
aa-f-262 · livello facile · dispensa
Un algoritmo con rapporto $\alpha=4$ per l'MCP, applicato a $G^{\boxtimes 2}$ e riportato su $G$, che rapporto garantisce su $G$?
  1. $16$
  2. $8$
  3. $\sqrt4=2$
  4. $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}$.
aa-f-263 · livello facile · dispensa
Il rapporto banale $n$ per l'MCP si ottiene restituendo che cosa?
  1. Il vertice di grado minimo con i suoi vicini
  2. Un solo vertice
  3. Tutti i vertici
  4. 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.
aa-f-264 · livello facile · dispensa
Perché un grafo planare non contiene una clique di $5$ vertici?
  1. Perché $K_5$ ha $10>3\cdot5-6=9$ spigoli
  2. Perché i grafi planari sono bipartiti
  3. Perché i grafi planari hanno grado massimo $4$
  4. Perché $\chi(G)\le4$ implica $n\le4$
Spiegazione. Un sottografo di un grafo planare è planare, e $K_5$ viola $m\le3n-6$: quindi $\omega(G)\le4$.
aa-f-265 · livello facile · dispensa
Come si risolve all'ottimo l'MCP su un grafo planare in tempo $O(n^4)$?
  1. Con il greedy per grado decrescente
  2. Con una visita in ampiezza del grafo
  3. Con l'algoritmo dei cinque colori
  4. Provando tutti gli insiemi di al più $4$ vertici
Spiegazione. Poiché $\omega(G)\le4$, basta enumerare i sottoinsiemi di al più $4$ vertici: sono $O(n^4)$.
aa-f-266 · livello facile · dispensa
Un grafo ha grado massimo $\Delta(G)=6$. Quale bound vale per $\omega(G)$?
  1. $\omega(G)\le3$
  2. $\omega(G)\le12$
  3. $\omega(G)\le7$
  4. $\omega(G)\le6$
Spiegazione. In una clique ogni vertice è adiacente agli altri $\omega(G)-1$, quindi $\omega(G)-1\le\Delta(G)$.
aa-f-267 · livello facile · dispensa
Perché l'MCP si risolve in tempo $O(n\,2^{\Delta}\Delta^2)$, con $\Delta=\Delta(G)$?
  1. Perché si usa la programmazione dinamica sui profitti
  2. Ogni clique sta in un vicinato chiuso
  3. Perché il greedy è ottimo sui grafi di grado limitato
  4. Perché $\omega(G)\le4$
Spiegazione. Per ogni vertice $v$ ci sono al più $2^{\Delta}$ sottoinsiemi di vicini, e controllare se uno è una clique costa $O(\Delta^2)$.
aa-f-268 · livello facile · dispensa
Perché i risultati negativi sull'MCP valgono anche per il problema dell'insieme stabile massimo (MSSP)?
  1. Perché $\alpha(G)=\omega(\overline G)$, con lo stesso $n$
  2. Perché ogni clique di $G$ è anche un insieme stabile di $G$
  3. Perché l'MSSP è più facile dell'MCP su ogni grafo
  4. 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.
aa-f-269 · livello facile · dispensa
Un grafo ha $n=20$ vertici e $\Delta(G)=4$. Quanti vertici ha almeno ogni insieme stabile massimale?
  1. $5$
  2. $20$
  3. $1$
  4. $4$
Spiegazione. Ogni vertice di $S$ esclude al più $\Delta(G)$ vicini: $n\le|S|(\Delta(G)+1)$, quindi $|S|\ge20/5=4$.
aa-f-270 · livello teorema · dispensa
Quale uguaglianza vale per il numero di clique del prodotto forte di due grafi qualunque $G$ e $H$?
  1. $\omega(G\boxtimes H)=\max\{\omega(G),\omega(H)\}$
  2. $\omega(G\boxtimes H)=\omega(G)^{\omega(H)}$
  3. $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$
  4. $\omega(G\boxtimes H)=\omega(G)+\omega(H)$
Spiegazione. Il prodotto di due clique è una clique ($\ge$), e ogni clique $K$ ha $|K|\le|p(K)|\max_u|K_u|\le\omega(G)\omega(H)$ ($\le$).
aa-f-271 · livello teorema · dispensa
Che cosa afferma il teorema di amplificazione sull'MCP?
  1. Ogni algoritmo polinomiale per l'MCP ha rapporto almeno $\frac43$
  2. Un $\alpha$ costante dà ogni costante $\beta>1$
  3. L'MCP ha una $2$-approssimazione polinomiale su ogni grafo
  4. Se l'MCP ha un PTAS allora necessariamente $P=NP$
Spiegazione. Con la potenza forte $G^{\boxtimes k}$ il rapporto scende ad $\alpha^{1/k}$, che per $k$ grande è $\le\beta$.
aa-f-272 · livello teorema · dispensa
Che cosa dicono i risultati di Håstad (1999) e Zuckerman (2007) sull'MCP, se $P\neq NP$?
  1. Nessun rapporto $n^{1-\varepsilon}$, per ogni $\varepsilon>0$
  2. L'MCP ha un FPTAS, ma non un algoritmo esatto polinomiale
  3. L'MCP ha una $2$-approssimazione polinomiale ma nessun PTAS
  4. Nessun rapporto $\le\log n$ è possibile, ma $\sqrt n$ sì
Spiegazione. Il rapporto banale è $n$: non si scende nemmeno a $n^{1-\varepsilon}$, quindi niente rapporto costante.
aa-f-273 · livello teorema · dispensa
Che cosa vale per l'MCP sui grafi planari?
  1. L'MCP resta non approssimabile entro $n^{1-\varepsilon}$
  2. $\omega(G)\le5$ e serve un algoritmo esponenziale
  3. L'MCP ha soltanto una $2$-approssimazione
  4. $\omega(G)\le4$ e l'MCP si risolve all'ottimo in $O(n^4)$
Spiegazione. Una clique di un grafo planare ha al più $4$ vertici: l'enumerazione dei sottoinsiemi di al più $4$ vertici è polinomiale.
aa-f-274 · livello teorema · dispensa
Quale garanzia ha il greedy che costruisce un insieme stabile massimale $S$, su ogni grafo?
  1. $\alpha(G)-|S|\le1$
  2. $\alpha(G)/|S|\le\omega(G)$
  3. $\alpha(G)/|S|\le\Delta(G)+1$
  4. $\alpha(G)/|S|\le2$
Spiegazione. $|S|\ge\frac{n}{\Delta(G)+1}$ e $\alpha(G)\le n$: il rapporto è al più $\Delta(G)+1$, costante sui grafi di grado limitato.
aa-f-275 · livello teorema · dispensa
Che cosa vale per l'approssimazione del problema dell'insieme stabile massimo (MSSP), se $P\neq NP$?
  1. È risolvibile all'ottimo in tempo polinomiale
  2. Nessun rapporto costante
  3. Ha una $2$-approssimazione polinomiale su ogni grafo
  4. Ha un PTAS, anche se non un FPTAS
Spiegazione. Per il passaggio al complementare l'MSSP eredita i limiti dell'MCP.
aa-f-276 · livello teorema · dispensa
Sui grafi di grado massimo $\Delta(G)\le\Delta$ costante, che cosa vale per l'MCP?
  1. Si risolve all'ottimo in tempo polinomiale
  2. Resta non approssimabile entro $n^{1-\varepsilon}$
  3. Ha solo una $(\Delta+1)$-approssimazione
  4. È NP-difficile anche per $\Delta=3$
Spiegazione. Con $\Delta$ costante, $2^{\Delta}\Delta^2$ è una costante: il tempo è lineare in $n$.
aa-f-277 · livello ipotesi · dispensa
Il teorema di amplificazione usa $G^{\boxtimes k}$ con $k$ fissato. Perché $k$ deve essere costante?
  1. Perché per $k$ grande $\omega(G)^k$ non è intero
  2. Perché il prodotto forte non è associativo
  3. Perché per $k\ge3$ il grafo non è più semplice
  4. Perché $G^{\boxtimes k}$ ha $n^k$ vertici
Spiegazione. Con $k$ che cresce con $n$ la taglia $n^k$ sarebbe superpolinomiale e l'algoritmo non sarebbe più polinomiale.
aa-f-278 · livello ipotesi · dispensa
Il teorema di amplificazione parte da una $\alpha$-approssimazione: quale ipotesi su $\alpha$ serve?
  1. $\alpha=n^{1-\varepsilon}$
  2. Nessuna: vale per ogni rapporto $\alpha(n)$
  3. $\alpha$ è una costante
  4. $\alpha<2$
Spiegazione. L'argomento fissa $k$ con $\alpha^{1/k}\le\beta$, possibile solo se $\alpha$ non cresce con $n$.
aa-f-279 · livello ipotesi · dispensa
Il risultato di Håstad e Zuckerman sull'MCP vale sotto quale ipotesi?
  1. Che l'algoritmo sia greedy
  2. $P\neq NP$
  3. Che il grafo sia planare
  4. Che $\Delta(G)$ sia limitato
Spiegazione. Senza $P\neq NP$ l'MCP potrebbe essere risolto in tempo polinomiale; sui planari e sui grafi di grado limitato è facile.
aa-f-280 · livello ipotesi · dispensa
Il bound $\omega(G)\le4$ vale per quali grafi?
  1. Per i grafi planari
  2. Per tutti i grafi con $\Delta(G)\le4$
  3. Per tutti i grafi
  4. Per i grafi bipartiti soltanto
Spiegazione. Viene da $K_5$ non planare; un grafo non planare può contenere clique grandi quanto si vuole.
aa-f-281 · livello ipotesi · dispensa
Il bound $|S|\ge\frac{n}{\Delta(G)+1}$ vale per quale tipo di insieme stabile $S$?
  1. Per ogni insieme stabile
  2. Solo per un insieme stabile massimo
  3. Solo per un insieme stabile trovato con la visita in ampiezza
  4. 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.
aa-f-282 · livello ipotesi · dispensa
L'algoritmo esatto $O(n\,2^{\Delta}\Delta^2)$ per l'MCP è polinomiale sotto quale ipotesi?
  1. Che valga $\omega(G)\le4$ per il grafo
  2. Che il grafo sia bipartito e connesso
  3. Che $\Delta(G)$ sia una costante
  4. Che il grafo sia planare e connesso
Spiegazione. Se $\Delta$ cresce con $n$ il fattore $2^{\Delta}$ diventa esponenziale.
aa-f-283 · livello ipotesi · dispensa
Perché il passaggio al complementare trasferisce un rapporto $n^{1-\varepsilon}$ dall'MCP all'MSSP?
  1. Perché $\Delta(\overline G)=\Delta(G)$
  2. Perché $\overline G$ ha gli stessi $n$ vertici
  3. Perché $\overline G$ ha meno spigoli
  4. Perché $\overline G$ è planare
Spiegazione. Il rapporto è espresso in funzione di $n$, che non cambia, e il complementare costa $O(n^2)$.
aa-f-284 · livello ipotesi · dispensa
L'uguaglianza $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$ richiede ipotesi su $G$ e $H$?
  1. No: vale per ogni coppia di grafi
  2. Sì: $G$ e $H$ devono essere planari
  3. Sì: $G=H$
  4. Sì: $G$ e $H$ devono avere lo stesso numero di vertici
Spiegazione. La proposizione vale per due grafi qualunque; il caso $G=H$ (le potenze forti) è quello usato nell'amplificazione.
aa-f-330 · livello teorema · dispensa
Nell'amplificazione, da una clique di $G^{\boxtimes k}$ di taglia $\ge\omega(G)^k/\alpha$ si ricava una clique di $G$ di taglia almeno:
  1. $\omega(G)^k/\alpha$
  2. $\omega(G)-\alpha$
  3. $\omega(G)/\alpha^{1/k}$
  4. $\omega(G)/\alpha$
Spiegazione. Una clique $K$ del prodotto ha una proiezione o una fibra di taglia $\ge|K|^{1/k}$: il rapporto diventa $\alpha^{1/k}$.
aa-f-331 · livello teorema · dispensa
Combinando l'amplificazione con i risultati di Håstad e Zuckerman, che cosa si conclude per l'MCP?
  1. Un FPTAS
  2. Nessun rapporto costante
  3. Un PTAS ma non un FPTAS
  4. Una $2$-approssimazione
Spiegazione. Un rapporto costante darebbe ogni rapporto $\beta>1$, cioè un PTAS; ma nemmeno $n^{1-\varepsilon}$ è raggiungibile.
aa-f-332 · livello teorema · dispensa
Quale disuguaglianza vale per ogni grafo $G$ fra numero di clique e grado massimo?
  1. $\omega(G)\le\Delta(G)+1$
  2. $\omega(G)\le\Delta(G)$
  3. $\omega(G)\ge\Delta(G)$
  4. $\omega(G)\le\frac{\Delta(G)}{2}$
Spiegazione. Un vertice di una clique ha almeno $\omega(G)-1$ vicini; $K_n$ mostra che $\omega(G)\le\Delta(G)$ è falso.
aa-f-333 · livello ipotesi · dispensa
Il limite $n^{1-\varepsilon}$ per l'MCP riguarda algoritmi con quale proprietà?
  1. Esatti
  2. Greedy
  3. Con garanzia additiva
  4. Polinomiali
Spiegazione. Un algoritmo esponenziale trova $\omega(G)$ esattamente; il limite vale per quelli polinomiali, se $P\neq NP$.
aa-f-334 · livello ipotesi · dispensa
La garanzia $\alpha(G)/|S|\le\Delta(G)+1$ del greedy è un rapporto costante sotto quale ipotesi?
  1. Che valga $\omega(G)\le4$
  2. Nessuna: è sempre costante
  3. Che $\Delta(G)$ sia costante
  4. Che il grafo sia planare
Spiegazione. Sui grafi generali $\Delta(G)$ può essere $n-1$ e la garanzia diventa $n$, coerente con i risultati negativi.
aa-f-335 · livello ipotesi · dispensa
Nel prodotto forte, due vertici $(u,x)$ e $(u,y)$ con la stessa prima coordinata sono adiacenti quando?
  1. Quando $u$ ha grado $>0$
  2. Quando $\{x,y\}\in F$
  3. Sempre, per ogni $x,y$
  4. Mai, perché $u=u$
Spiegazione. Con $u=v$ la prima condizione è soddisfatta; resta la seconda, $x=y$ (escluso, vertici distinti) o $\{x,y\}\in F$.
aa-f-357 · livello teorema · dispensa
Quale grafo completo è il più grande contenuto in un grafo planare?
  1. $K_5$
  2. $K_3$
  3. $K_6$
  4. $K_4$
Spiegazione. $K_5$ non è planare, $K_4$ sì: quindi $\omega(G)\le4$ sui grafi planari.

6. TSP: il caso generale e il caso metrico (44)

aa-f-021 · livello teorema · dispensa
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?
  1. Il TSP generale non ha approssimazioni costanti; sul TSP metrico $DT$ ha rapporto $2$ e $CH$ rapporto $\frac32$
  2. Il TSP generale non ha approssimazioni costanti; sul TSP metrico $DT$ ha rapporto $\frac32$ e $CH$ rapporto $2$
  3. Il TSP generale ha una $2$-approssimazione, $DT$; sul TSP metrico $CH$ ha rapporto $\frac32$
  4. 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.
aa-f-022 · livello ipotesi · dispensa
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)$?
  1. $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
  2. $d(T)\le z(I)/2$; il circuito euleriano dell'albero raddoppiato è lungo $2d(T)$; le distanze sono simmetriche
  3. Il giro del nearest neighbour è lungo al più $2z(I)$; ogni città ha grado pari; le distanze sono simmetriche
  4. $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$.
aa-f-023 · livello ipotesi · dispensa
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)$?
  1. $d(T)\le z(I)$; $d(M)\le d(T)$; le città di grado dispari di $T$ sono in numero dispari
  2. $d(T)\le z(I)$; il circuito dell'albero raddoppiato è lungo $2d(T)$; le distanze sono simmetriche
  3. $d(T)\le z(I)$; $d(M)\le z(I)/2$; le scorciatoie non allungano il circuito euleriano di $T\cup M$
  4. $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.
aa-f-072 · livello ipotesi · dispensa
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?
  1. Distanza $2$ sui lati e $1$ sulle coppie non adiacenti
  2. 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
  3. Distanza $1$ su tutte le coppie: ogni giro è ottimo
  4. 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.
aa-f-073 · livello facile · dispensa
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?
  1. Le città nel piano con le distanze euclidee
  2. Le istanze con distanze intere qualsiasi
  3. Le istanze con $d_{ij}\in\{1,2\}$ e $d_{ij}\ne d_{ji}$
  4. 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.
aa-f-074 · livello facile · dispensa
Il TSP generale non ha approssimazioni costanti (se $P\neq NP$), il TSP metrico sì. Che cosa si sa della complessità del TSP metrico?
  1. È polinomiale, perché la disuguaglianza triangolare permette le scorciatoie
  2. È polinomiale sulle istanze euclidee, NP-difficile sulle altre
  3. Non ammette nemmeno lui approssimazioni costanti
  4. 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.
aa-f-075 · livello facile · dispensa
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)$?
  1. $DT(I)\le 7$ e $z(I)\ge 14$
  2. $DT(I)\le\frac{21}{2}$ e $z(I)\ge 7$
  3. $DT(I)\le 14$ e $z(I)\ge 7$
  4. $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)$.
aa-f-076 · livello facile · dispensa
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à?
  1. $0$
  2. $4$
  3. $3$
  4. $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.
aa-f-077 · livello ipotesi · dispensa
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?
  1. 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)$
  2. La disuguaglianza triangolare permette di accorciare l'albero
  3. Il giro ottimo contiene sempre l'albero ricoprente minimo
  4. 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.
aa-f-078 · livello ipotesi · dispensa
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$?
  1. Perché $M$ ha la metà dei lati del giro ottimo
  2. Perché ogni lato di $M$ è più corto di ogni lato del giro
  3. Perché $M$ è contenuto nell'albero ricoprente minimo
  4. 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à.
aa-f-079 · livello facile · dispensa
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)$?
  1. $\frac{28}{3}\le z(I)\le 10$
  2. $z(I)\ge 14$
  3. $10\le z(I)\le 14$
  4. $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$).
aa-f-080 · livello facile · dispensa
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?
  1. $2$ per ogni $n$
  2. $\frac{14}{9}$, e tende a $2$
  3. $\frac{14}{9}$, e tende a $\frac32$
  4. $\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.
aa-f-117 · livello teorema · dispensa
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$?
  1. Per la disuguaglianza triangolare ogni scorciatoia $d_{u_0u_q}$ è al più la lunghezza del tratto di $W$ che sostituisce
  2. Perché $\sigma$ ha meno città di $W$
  3. Perché le distanze sono tutte uguali
  4. 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.
aa-f-118 · livello facile · dispensa
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?
  1. Entrambi raddoppiano gli spigoli di $T$
  2. Doppio albero: aggiunge un abbinamento; Christofides: raddoppia $T$
  3. Nessuno dei due usa un multigrafo euleriano
  4. 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.
aa-f-119 · livello teorema · dispensa
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?
  1. Che il double tree è migliore di Christofides
  2. Che le scorciatoie possono allungare il giro
  3. Che la garanzia $\frac32$ di Christofides è stretta: l'abbinamento può costare quasi metà del giro ottimo
  4. 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.
aa-f-120 · livello ipotesi · dispensa
La garanzia $CH(I)\le\frac32z(I)$ di Christofides usa la disuguaglianza triangolare. Che cosa succede per il TSP generale, senza questa ipotesi?
  1. Il TSP generale diventa polinomiale
  2. Nessun algoritmo polinomiale ha un rapporto costante, se P $\ne$ NP
  3. Christofides resta una $\frac32$-approssimazione
  4. 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.
aa-f-190 · livello facile · dispensa
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?
  1. $21$
  2. $20$
  3. $29$
  4. $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$.
aa-f-191 · livello ipotesi · dispensa
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}$)?
  1. Perché il ciclo hamiltoniano è facile sui grafi metrici
  2. Perché nel TSP metrico le distanze possono essere $0$
  3. Le istanze costruite violano la disuguaglianza triangolare
  4. 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.
aa-f-192 · livello facile · dispensa
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?
  1. No: la condizione riguarda solo le città vicine
  2. No: vale $9\le5+4$, con l'uguaglianza ammessa
  3. Sì: $d_{15}$ non è strettamente minore di $d_{12}+d_{25}$
  4. 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.
aa-f-193 · livello facile · dispensa
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?
  1. Le scorciatoie (saltare città già visitate) non allungano il cammino
  2. Rende il TSP risolvibile in tempo polinomiale
  3. Garantisce che l'albero ricoprente minimo sia già un giro
  4. 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.
aa-f-194 · livello facile · dispensa
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. $\{1,2\},\{3,4\},\{1,4\}$, con $d(T)=8$
  2. $\{1,2\},\{1,3\},\{2,3\}$, con $d(T)=8$
  3. $\{1,2\},\{3,4\}$, con $d(T)=4$
  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à.
aa-f-195 · livello facile · dispensa
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. $(1,3,4,2)$
  2. $(1,2,1,3,4)$
  3. $(1,2,3,4)$
  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$.
aa-f-196 · livello facile · dispensa
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. $(1,2,4,3)$, lungo $12$
  2. $(1,2,3,4)$, lungo $11$
  3. $(1,2,3,4)$, lungo $14$
  4. $(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.
aa-f-197 · livello facile · dispensa
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?
  1. L'ultima copia dello spigolo verso il padre è un ponte, usata per ultima
  2. Perché l'algoritmo di Kruskal restituisce sempre un cammino
  3. Perché nell'albero raddoppiato ogni città ha grado $2$
  4. 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.
aa-f-198 · livello facile · dispensa
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. $(1,2,3,4)$, lungo $11$
  2. $(1,3,4,2)$, lungo $15$
  3. $(1,2,1,3,4)$, lungo $14$
  4. $(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ì.
aa-f-199 · livello facile · dispensa
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?
  1. Perché le foglie di un albero sono sempre in numero pari
  2. Perché l'algoritmo blossom lo richiede
  3. I gradi di un grafo sommano al doppio del numero di spigoli
  4. 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).
aa-f-200 · livello facile · dispensa
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?
  1. $z(I)\ge14.5$
  2. $z(I)\ge20$
  3. $z(I)\ge29$
  4. $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.
aa-f-201 · livello teorema · dispensa
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$?
  1. L'MST è la stella; foglie consecutive in preordine non sono unite da $P$
  2. Perché l'albero minimo è il cammino $P$, percorso due volte
  3. Perché le scorciatoie fanno risparmiare $b-a$ a ogni passo
  4. 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)$.
aa-f-285 · livello facile · dispensa
Da quale problema NP-completo si riduce per mostrare che il TSP generale non ha rapporto costante (se $P\neq NP$)?
  1. Il ciclo hamiltoniano
  2. Il bin packing
  3. La $2$-colorabilità
  4. 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.
aa-f-286 · livello facile · dispensa
Quale proprietà delle distanze rende metrica un'istanza del TSP?
  1. $d_{ij}\le d_{ik}\cdot d_{kj}$ per ogni terna
  2. $d_{ij}=d_{ik}+d_{kj}$ per ogni terna
  3. $d_{ij}\ge d_{ik}+d_{kj}$ per ogni terna
  4. $d_{ij}\le d_{ik}+d_{kj}$ per ogni terna
Spiegazione. È la disuguaglianza triangolare: andare direttamente da $i$ a $j$ non costa più che passare per $k$.
aa-f-287 · livello facile · dispensa
Perché il costo di un albero ricoprente minimo $T$ è un lower bound per il TSP?
  1. Perché vale la disuguaglianza triangolare
  2. Perché $T$ ha sempre esattamente $n$ archi
  3. Un giro ottimo meno un arco è un albero
  4. Perché ogni albero ricoprente è un giro
Spiegazione. Un giro ottimo meno un arco è un cammino hamiltoniano, cioè un albero ricoprente: $d(T)\le z(I)$, anche senza metrica.
aa-f-288 · livello facile · dispensa
Nell'algoritmo double tree, che cosa si fa con gli archi dell'albero ricoprente minimo?
  1. Si ordinano per costo decrescente e si scartano
  2. Si raddoppiano, ottenendo un multigrafo euleriano
  3. Si tolgono quelli più lunghi dell'albero
  4. Si accoppiano i vertici di grado dispari
Spiegazione. Raddoppiando gli archi ogni vertice ha grado pari: c'è un circuito euleriano di costo $2d(T)$, poi si fanno le scorciatoie.
aa-f-289 · livello facile · dispensa
Che cosa sono le «scorciatoie» applicate al circuito euleriano?
  1. Si saltano le città già visitate
  2. Si tolgono gli archi più lunghi del circuito
  3. Si scambiano due archi incrociati (2-opt)
  4. Si aggiunge un accoppiamento perfetto
Spiegazione. Dal cammino chiuso si tiene solo la prima visita di ogni città; con la metrica il costo non aumenta.
aa-f-290 · livello facile · dispensa
Un'istanza metrica ha un albero ricoprente minimo di costo $d(T)=30$. Quanto costa al più il giro del double tree?
  1. $45$
  2. $30$
  3. $90$
  4. $60$
Spiegazione. Il circuito euleriano costa $2d(T)=60$ e le scorciatoie non lo allungano: $DT(I)\le60$.
aa-f-291 · livello facile · dispensa
Nell'algoritmo di Christofides, quali vertici si accoppiano con un accoppiamento perfetto di costo minimo?
  1. Le foglie dell'albero soltanto
  2. I vertici di grado pari dell'albero
  3. I vertici di grado dispari dell'albero
  4. Tutti i vertici dell'albero
Spiegazione. Aggiungendo l'accoppiamento dei vertici dispari di $T$ ogni grado diventa pari e il multigrafo è euleriano.
aa-f-292 · livello facile · dispensa
Perché il numero di vertici di grado dispari di un albero è pari?
  1. Perché un albero ha esattamente due foglie
  2. Perché la somma dei gradi è pari
  3. Perché un albero ha sempre $n-1$ archi
  4. Perché ogni albero è un grafo bipartito
Spiegazione. In ogni grafo $\sum_v\deg(v)=2m$ è pari, quindi i gradi dispari sono in numero pari: l'accoppiamento perfetto esiste.
aa-f-293 · livello facile · dispensa
Un'istanza metrica ha $z(I)=40$. Quanto costa al più un accoppiamento perfetto minimo di un insieme pari $O$ di città?
  1. $20$
  2. $40$
  3. $\frac{40}{3}$
  4. $80$
Spiegazione. Il giro ottimo, ristretto a $O$ con scorciatoie, si divide in due accoppiamenti perfetti; il migliore costa al più $z(I)/2=20$.
aa-f-294 · livello facile · dispensa
Su un'istanza metrica con $z(I)=24$, quanto costa al più il giro di Christofides?
  1. $48$
  2. $30$
  3. $24$
  4. $36$
Spiegazione. $CH(I)\le d(T)+d(M)\le z(I)+\frac{z(I)}{2}=36$.
aa-f-295 · livello facile · dispensa
Le istanze tight del double tree hanno rapporto $\frac{2n}{n+2}$. Quanto vale per $n=7$?
  1. $\frac{16}{9}$
  2. $\frac{9}{7}$
  3. $\frac{14}{9}$
  4. $\frac{7}{9}$
Spiegazione. $\frac{2\cdot7}{7+2}=\frac{14}{9}\approx1{,}56$; al crescere di $n$ il rapporto tende a $2$.
aa-f-296 · livello facile · dispensa
Che cosa hanno in comune double tree e Christofides?
  1. Entrambi accoppiano i vertici dispari
  2. Albero ricoprente minimo, circuito euleriano
  3. Entrambi usano il 2-opt
  4. Entrambi sono esatti sulle istanze metriche
Spiegazione. Differiscono solo nel modo di rendere euleriano l'albero: archi raddoppiati (DT) o accoppiamento dei vertici dispari (CH).
aa-f-297 · livello facile · dispensa
Le istanze tight di Christofides mostrano che cosa?
  1. Che il rapporto $\frac32$ non si può migliorare
  2. Che Christofides è un algoritmo ottimo
  3. Che il double tree è sempre migliore
  4. Che il TSP metrico ha un PTAS
Spiegazione. Su una famiglia di istanze metriche il rapporto tende a $\frac32$: la garanzia è stretta.
aa-f-298 · livello facile · dispensa
Un multigrafo connesso ha un circuito euleriano se e solo se:
  1. ogni vertice ha grado dispari
  2. è un albero
  3. ha un numero pari di vertici
  4. ogni vertice ha grado pari
Spiegazione. È il teorema di Eulero: è proprio ciò che raddoppio degli archi e accoppiamento dei dispari garantiscono.
aa-f-299 · livello teorema · dispensa
Quale garanzia ha il double tree sulle istanze metriche?
  1. $DT(I)\le z(I)+2$
  2. $DT(I)\le\frac43z(I)$
  3. $DT(I)\le2z(I)$
  4. $DT(I)\le\frac32z(I)$
Spiegazione. $DT(I)\le2d(T)\le2z(I)$: scorciatoie (metrica) e lower bound dell'albero.
aa-f-300 · livello ipotesi · dispensa
Le scorciatoie non allungano il cammino: quale ipotesi serve?
  1. Un albero ricoprente unico
  2. La disuguaglianza triangolare
  3. Distanze tutte uguali
  4. Un numero dispari di città
Spiegazione. Saltare una città sostituisce due archi con uno, che per la triangolare non costa di più.

7. Approssimazione per $P\|C_{\max}$ (42)

aa-f-024 · livello ipotesi · dispensa
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)$?
  1. $S_\ell\le\frac1m\sum_{j\ne\ell}t_j$; $z(I)\ge\frac1m\sum_j t_j$; $z(I)\ge 2t_\ell$
  2. $\ell$ è il lavoro più lungo; $z(I)=\frac1m\sum_j t_j$; $z(I)\ge t_\ell$
  3. I lavori sono ordinati per durata non crescente; $z(I)\ge t_\ell$; $S_\ell\le z(I)$
  4. $S_\ell\le\frac1m\sum_{j\ne\ell}t_j$; $z(I)\ge\frac1m\sum_j t_j$; $z(I)\ge t_\ell$
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$.
aa-f-025 · livello facile · dispensa
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?
  1. $\frac43$
  2. $\frac54$
  3. $\frac76$
  4. $\frac32$
Spiegazione. $\frac43-\frac1{3m}=\frac43-\frac16=\frac76$. Con una lista qualsiasi $LIST$ garantisce $2-\frac12=\frac32$.
aa-f-026 · livello teorema · dispensa
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?
  1. Nessuna delle due è raggiunta: i rapporti sono solo approcciati al crescere di $n$
  2. Entrambe sono tight: per ogni $m\ge 2$ esistono istanze che raggiungono esattamente i due rapporti
  3. Entrambe sono tight solo per $m=2$; per $m\ge 3$ i rapporti sono più bassi
  4. 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$).
aa-f-081 · livello facile · dispensa
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$?
  1. $8$ e $8$
  2. $9$ e $7$
  3. $8$ e $7$
  4. $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.
aa-f-082 · livello facile · dispensa
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?
  1. $LPT$ è esponenziale, $LIST$ polinomiale
  2. $LIST$ può lavorare online, assegnando i lavori man mano che arrivano; $LPT$ deve conoscere tutti i lavori per ordinarli
  3. $LIST$ richiede di conoscere tutti i lavori, $LPT$ no
  4. $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}$.
aa-f-083 · livello teorema · dispensa
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$?
  1. $\ell$ va sulla macchina meno carica, il cui carico è al più la media dei carichi, che contengono solo lavori diversi da $\ell$
  2. Perché $\ell$ è il lavoro più lungo
  3. Perché i lavori sono ordinati per durata non crescente
  4. 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.
aa-f-084 · livello facile · dispensa
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$?
  1. $19$
  2. $5$
  3. $\frac{19}{3}$
  4. $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$.
aa-f-085 · livello facile · dispensa
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?
  1. $5$ e $4$: rapporto $\frac54$
  2. $6$ e $3$: rapporto $2$
  3. $5$ e $3$: rapporto $\frac53=2-\frac13$
  4. $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.
aa-f-086 · livello facile · dispensa
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?
  1. $12$ e $9$
  2. $11$ e $9$: rapporto $\frac{11}{9}=\frac43-\frac19$
  3. $9$ e $9$: $LPT$ è ottimo
  4. $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$.
aa-f-087 · livello facile · dispensa
Nello scheduling $P\,||\,C_{\max}$, $LIST$ garantisce $2-\frac1m$ e $LPT$ garantisce $\frac43-\frac1{3m}$. Quanto valgono con $m=4$ macchine?
  1. $\frac74$ e $\frac54$
  2. $\frac74$ e $\frac43$
  3. $\frac32$ e $\frac54$
  4. $2$ e $\frac43$
Spiegazione. $2-\frac14=\frac74$ e $\frac43-\frac1{12}=\frac{15}{12}=\frac54$. Al crescere di $m$ le garanzie tendono a $2$ e a $\frac43$.
aa-f-088 · livello facile · dispensa
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}$?
  1. $LIST(I)=\mathrm{LB}$ per ogni lista
  2. $LIST(I)\le\mathrm{LB}+1$
  3. $LIST(I)\ge 2\,\mathrm{LB}$ per qualche istanza
  4. $LIST(I)\le\frac1m\sum_jt_j+\max_jt_j\le 2\,\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$.
aa-f-089 · livello facile · dispensa
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$?
  1. $LIST$ $3$, $LPT$ $3$
  2. $LIST$ $4$, $LPT$ $2$
  3. $LIST$ $3$, $LPT$ $2$
  4. $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.
aa-f-121 · livello facile · dispensa
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?
  1. $z(I)\ge m$ e $z(I)\ge n$
  2. $z(I)\ge\mathscr{A}(I)$
  3. $z(I)\ge\max_jt_j$ e $z(I)\ge\frac1m\sum_jt_j$
  4. $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$.
aa-f-122 · livello ipotesi · dispensa
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?
  1. Le macchine hanno velocità diverse
  2. I lavori sono esaminati per durata non crescente, quindi l'ultimo lavoro assegnato è corto rispetto all'ottimo
  3. I lavori sono esaminati in ordine casuale
  4. 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.
aa-f-147 · livello facile · dispensa
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?
  1. $8$
  2. $7$
  3. $9$
  4. $14$
Spiegazione. $2\to M_1$, $3\to M_2$, $4\to M_1$ (carico $6$), $5\to M_2$ (carico $8$): makespan $8$. L'ottimo $\{2,5\},\{3,4\}$ vale $7$.
aa-f-148 · livello facile · dispensa
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$?
  1. Perché la lista è ordinata per tempi decrescenti
  2. Perché le macchine sono vuote all'inizio
  3. Perché il lavoro più lungo è sempre l'ultimo
  4. 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$.
aa-f-149 · livello facile · dispensa
La regola LPT per $P\,||\,C_{\max}$ è $LIST$ con la lista ordinata per tempi non crescenti. Con $m=2$ e tempi $\{2,3,4,5\}$, che makespan ottiene?
  1. $6$
  2. $9$
  3. $7$
  4. $8$
Spiegazione. Ordine $5,4,3,2$: $5\to M_1$, $4\to M_2$, $3\to M_2$ (carico $7$), $2\to M_1$ (carico $7$): makespan $7$, l'ottimo. La lista crescente dava $8$.
aa-f-150 · livello facile · dispensa
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?
  1. $S_\ell\le24$, makespan $\le27$
  2. $S_\ell\le8$, makespan $\le11$
  3. $S_\ell\le9$, makespan $\le12$
  4. $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$.
aa-f-151 · livello teorema · dispensa
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)$?
  1. $\frac1m\sum_jt_j\le z(I)$ e $t_\ell\le z(I)$
  2. $t_\ell\le\frac1m\sum_jt_j$ e $z(I)\le\sum_jt_j$
  3. $LIST$ è ottimo per $m=1$ e $t_\ell\le1$
  4. $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$.
aa-f-301 · livello facile · dispensa
Come assegna i lavori l'algoritmo $LIST$?
  1. Per durata decrescente, a turno
  2. Risolvendo un modello PLI
  3. In ordine di lista, alla meno carica
  4. Ciascuno alla macchina più carica
Spiegazione. $LIST$ prende i lavori nell'ordine dato e mette ognuno sulla macchina che si libera per prima.
aa-f-302 · livello facile · dispensa
In che cosa $LPT$ differisce da $LIST$?
  1. Sposta i lavori dopo l'assegnamento iniziale
  2. Ordina prima i lavori per durata non crescente
  3. Assegna ogni lavoro alla macchina più carica
  4. Usa una sola macchina per tutti i lavori
Spiegazione. $LPT$ è $LIST$ con la lista dei lavori per durata decrescente: i lavori lunghi vanno per primi.
aa-f-303 · livello facile · dispensa
Quale lower bound elementare vale per $z(I)$ in $P\,||\,C_{\max}$?
  1. $\max\{\max_j t_j,\ \sum_j t_j/m\}$
  2. $\min_j t_j$, il lavoro più corto
  3. $\sum_j t_j$, la somma delle durate
  4. $\max_j t_j/m$
Spiegazione. Il makespan è almeno il lavoro più lungo e almeno il carico medio delle macchine.
aa-f-304 · livello facile · dispensa
Durate $t=(5,4,3,3,3)$ su $m=2$ macchine. Quanto vale il lower bound $\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}$?
  1. $5$
  2. $18$
  3. $8$
  4. $9$
Spiegazione. $\sum_j t_j=18$, $18/2=9$, $\max_j t_j=5$: il bound è $9$ (ed è raggiunto, $\{5,4\},\{3,3,3\}$).
aa-f-305 · livello facile · dispensa
Con $m=4$ macchine, quale garanzia ha $LIST$?
  1. $2$
  2. $\frac{5}{4}$
  3. $\frac74$
  4. $\frac43$
Spiegazione. $LIST(I)/z(I)\le2-\frac1m=2-\frac14=\frac74$.
aa-f-306 · livello facile · dispensa
Quale rapporto nel caso peggiore garantisce l'algoritmo $LPT$ su tre macchine parallele identiche?
  1. $\frac{10}{9}$
  2. $\frac{11}{9}$
  3. $\frac43$
  4. $\frac53$
Spiegazione. $\frac43-\frac{1}{3m}=\frac43-\frac19=\frac{11}{9}$.
aa-f-307 · livello facile · dispensa
Perché il lavoro $\ell$ che finisce per ultimo con $LIST$ inizia al più al carico medio degli altri lavori?
  1. Va sulla macchina meno carica
  2. Perché è il lavoro più corto
  3. Perché $LIST$ ordina i lavori
  4. Perché tutte le macchine hanno lo stesso carico
Spiegazione. Al momento dell'assegnamento la macchina scelta ha il carico minimo, e il minimo non supera la media $\frac1m\sum_{j\neq\ell}t_j$.
aa-f-308 · livello facile · dispensa
La garanzia $2-\frac1m$ di $LIST$ è tight: che cosa significa?
  1. $LIST$ ha sempre rapporto esattamente $2-\frac1m$
  2. $LIST$ è ottimo su ogni istanza con $m=2$
  3. Esiste un'istanza con rapporto uguale a $2$
  4. Per ogni $m$ un'istanza raggiunge $2-\frac1m$
Spiegazione. La proposizione 7.3 dà, per ogni $m\ge2$, un'istanza e una lista che raggiungono il bound.
aa-f-309 · livello facile · dispensa
Per $m=2$ l'istanza tight di $LPT$ ha rapporto pari a quanto?
  1. $\frac32$
  2. $\frac65$
  3. $\frac76$
  4. $\frac43$
Spiegazione. $\frac43-\frac16=\frac76$; per esempio durate $(3,3,2,2,2)$: $LPT=7$, ottimo $6$.
aa-f-310 · livello facile · dispensa
Durate $(3,3,2,2,2)$ su $m=2$ macchine. Quanto vale il makespan di $LPT$?
  1. $12$
  2. $7$
  3. $6$
  4. $8$
Spiegazione. $LPT$: $3\to M_1$, $3\to M_2$, $2\to M_1$ ($5$), $2\to M_2$ ($5$), $2\to M_1$ ($7$). L'ottimo è $6$: $\{3,3\},\{2,2,2\}$.
aa-f-311 · livello facile · dispensa
Due macchine e la lista di lavori di durate $2,2,2,2,4$, in quest'ordine: che makespan produce $LIST$?
  1. $8$
  2. $6$
  3. $12$
  4. $4$
Spiegazione. $LIST$ mette i quattro lavori da $2$ a coppie ($4$ e $4$), poi il $4$ su una macchina: $8$. L'ottimo è $6$.
aa-f-312 · livello facile · dispensa
Perché $LPT$ ha una garanzia migliore di $LIST$?
  1. Perché $LPT$ è esatto
  2. Perché $LPT$ usa più macchine
  3. Perché $LPT$ ignora i lavori corti
  4. L'ultimo lavoro è corto
Spiegazione. Con i lavori per durata decrescente, se il lavoro critico è lungo l'ottimo ne mette pochi per macchina e $LPT$ è ottimo; altrimenti è corto.
aa-f-313 · livello teorema · dispensa
Quale garanzia ha $LIST$ per ogni istanza e ogni lista?
  1. $LIST(I)\le z(I)+\max_jt_j$, non relativa
  2. $LIST(I)\le\frac32z(I)$
  3. $LIST(I)\le\left(2-\frac1m\right)z(I)$
  4. $LIST(I)\le\frac43z(I)$
Spiegazione. $C_{\max}=S_\ell+t_\ell\le\frac1m\sum_{j\neq\ell}t_j+t_\ell\le z(I)+(1-\frac1m)t_\ell\le(2-\frac1m)z(I)$.
aa-f-314 · livello ipotesi · dispensa
La garanzia $2-\frac1m$ di $LIST$ dipende dall'ordine della lista?
  1. Sì: solo per $m=2$
  2. No: vale per ogni lista
  3. Sì: solo per durate decrescenti
  4. Sì: solo per durate crescenti
Spiegazione. La dimostrazione usa solo che ogni lavoro va sulla macchina meno carica; l'ordine decrescente dà la garanzia migliore di $LPT$.
aa-f-315 · livello ipotesi · dispensa
La tightness di $2-\frac1m$ per $LIST$ è dimostrata per quali $m$?
  1. Per ogni $m\ge2$
  2. Solo per $m=2$
  3. Solo per $m$ pari
  4. Solo per $m\le3$
Spiegazione. Per ogni $m\ge2$ la proposizione 7.3 costruisce un'istanza $I_m$ con rapporto esattamente $2-\frac1m$.
aa-f-348 · livello facile · dispensa
Quanto vale la garanzia di $LPT$ con $m=2$ macchine?
  1. $\frac32$
  2. $\frac43$
  3. $\frac54$
  4. $\frac76$
Spiegazione. $\frac43-\frac{1}{3\cdot2}=\frac76$.
aa-f-349 · livello facile · dispensa
Su due macchine, quale rapporto nel caso peggiore ha la regola $LIST$?
  1. $\frac76$
  2. $\frac43$
  3. $\frac32$
  4. $2$
Spiegazione. $2-\frac12=\frac32$.
aa-f-350 · livello facile · dispensa
A che valore tende la garanzia di $LIST$ quando il numero di macchine $m$ cresce?
  1. $\frac32$
  2. $2$
  3. $\frac43$
  4. $1$
Spiegazione. $2-\frac1m\to2$; quella di $LPT$, $\frac43-\frac{1}{3m}$, tende a $\frac43$.
aa-f-351 · livello facile · dispensa
Tre macchine e lavori lunghi $7,2,2,2$: quale lower bound elementare si ottiene per il makespan ottimo?
  1. $7$
  2. $5$
  3. $13$
  4. $4$
Spiegazione. $\sum_jt_j=13$, $\lceil13/3\rceil=5$, $\max_jt_j=7$: il bound è $7$, ed è l'ottimo.
aa-f-352 · livello facile · dispensa
Durate $(5,4,3,3,3)$ su $m=2$ macchine: che makespan dà $LPT$?
  1. $9$
  2. $11$
  3. $8$
  4. $10$
Spiegazione. $5\to M_1$, $4\to M_2$, $3\to M_2$ ($7$), $3\to M_1$ ($8$), $3\to M_2$ ($10$). L'ottimo è $9$.
aa-f-353 · livello facile · dispensa
Con $m=3$ e somma delle durate degli altri lavori pari a $24$, quando inizia al più l'ultimo lavoro $\ell$ di $LIST$?
  1. All'istante $12$
  2. All'istante $6$
  3. All'istante $8$
  4. All'istante $24$
Spiegazione. $S_\ell\le\frac1m\sum_{j\neq\ell}t_j=24/3=8$.
aa-f-354 · livello facile · dispensa
Che errore fa chi dice che $LPT$ è ottimo perché mette per primi i lavori lunghi?
  1. $LPT$ non è polinomiale
  2. $LPT$ può non essere ottimo
  3. Nessuno: $LPT$ è ottimo
  4. $LPT$ ha rapporto $2$
Spiegazione. Le istanze tight mostrano che $LPT$ può sbagliare: $P\,||\,C_{\max}$ è NP-difficile.
aa-f-355 · livello facile · dispensa
Le istanze tight di $LPT$ hanno $2m+1$ lavori. Quanti lavori hanno con $m=3$?
  1. $7$
  2. $6$
  3. $9$
  4. $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)$?
  1. $72\le z(I)\le 128$
  2. $72\le z(I)\le 96$
  3. $96\le z(I)\le 128$
  4. $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)$?
  1. $z(I)=16$
  2. $4\le z(I)\le 16$
  3. $4\le z(I)\le 8$
  4. $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?
  1. $\frac{9}{5}$ e $\frac{4}{5}$
  2. $\frac{5}{9}$ e $\frac{4}{9}$
  3. $\frac{9}{5}$ e $\frac{4}{9}$
  4. $\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?
  1. $\frac{5}{36}$ e $\frac{41}{36}$
  2. $\frac{41}{36}$ e $\frac{5}{41}$
  3. $\frac{36}{41}$ e $\frac{5}{36}$
  4. $\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)$?
  1. $33$
  2. $27$
  3. $26$
  4. $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)$?
  1. $33$
  2. $43$
  3. $41$
  4. $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$?
  1. $p'=(1,0,0,0)$
  2. $p'=(4,3,2,3)$
  3. $p'=(4,2,1,2)$
  4. $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$?
  1. $p'=(5,5,4,1)$
  2. $p'=(6,6,5,2)$
  3. $p'=(1,1,1,0)$
  4. $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)$?
  1. $FP^{\varepsilon}(I)=8$, $z(I)=78$
  2. $FP^{\varepsilon}(I)=78$, $z(I)=79$
  3. $FP^{\varepsilon}(I)=78$, $z(I)=156$
  4. $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)$?
  1. $FP^{\varepsilon}(I)=82$, $z(I)=164$
  2. $FP^{\varepsilon}(I)=9$, $z(I)=82$
  3. $FP^{\varepsilon}(I)=82$, $z(I)=82$
  4. $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)?
  1. $bin=(1,2,2,3,1,4,4)$
  2. $bin=(1,2,2,3,3,4,4)$
  3. $bin=(1,2,1,3,3,2,4)$
  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)?
  1. $bin=(1,1,2,3,4,2,4)$
  2. $bin=(1,1,2,3,4,2,3)$
  3. $bin=(1,1,2,3,4,5,5)$
  4. $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?
  1. $4$, $6$
  2. $6$, $5$
  3. $5$, $4$
  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?
  1. $6$, $4$
  2. $5$, $4$
  3. $6$, $5$
  4. $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?
  1. $NF=5$, $FF=5$, $BF=5$, $WF=5$
  2. $NF=6$, $FF=5$, $BF=5$, $WF=6$
  3. $NF=5$, $FF=6$, $BF=5$, $WF=5$
  4. $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?
  1. $NF=6$, $FF=5$, $BF=5$, $WF=5$
  2. $NF=5$, $FF=6$, $BF=5$, $WF=5$
  3. $NF=6$, $FF=5$, $BF=5$, $WF=6$
  4. $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?
  1. $3$
  2. $4$
  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 $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?
  1. $3$
  2. $5$
  3. $4$
  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?
  1. $3n-6=51$: può essere planare
  2. $3n-6=51$: non è planare
  3. $3n-6=54$: non è planare
  4. $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?
  1. $3n-6=39$: può essere planare
  2. $3n-6=39$: non è planare
  3. $3n-6=36$: non è planare
  4. $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.

5. Clique massima: limiti dell'approssimazione (2)

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?
  1. $16$ vertici e $\omega=5$
  2. $16$ vertici e $\omega=2$
  3. $16$ vertici e $\omega=4$
  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?
  1. $8$ vertici e $\omega=6$
  2. $16$ vertici e $\omega=5$
  3. $16$ vertici e $\omega=3$
  4. $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?
  1. $|S|=3$, bound $3$
  2. $|S|=2$, bound $2$
  3. $|S|=4$, bound $2$
  4. $|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?
  1. $|S|=5$, bound $2$
  2. $|S|=4$, bound $2$
  3. $|S|=5$, bound $3$
  4. $|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?
  1. $15$
  2. $17$
  3. $32$
  4. $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?
  1. $34$
  2. $15$
  3. $18$
  4. $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?
  1. $18$
  2. $36$
  3. $33$
  4. $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?
  1. $18$
  2. $35$
  3. $34$
  4. $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?
  1. $11$, $11$
  2. $10$, $11$
  3. $10$, $10$
  4. $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?
  1. $16$, $12$
  2. $12$, $16$
  3. $12$, $12$
  4. $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?
  1. $\frac{15}{16}$
  2. $\frac{7}{6}$
  3. $\frac{16}{15}$
  4. $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?
  1. $\frac{7}{6}$
  2. $\frac{10}{11}$
  3. $\frac{11}{10}$
  4. $\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}$.