Esercizi · Principi degli algoritmi di approssimazione¶
Esercizi · Capitolo 34 · ogni soluzione si apre con un clic · Capitolo 34: Principi · Eserciziario, volume 5 (PDF)
Definizioni usate in questi esercizi
Le misure del capitolo Principi degli algoritmi di approssimazione, per un algoritmo \(\mathscr{A}\) di valore \(\mathscr{A}(I)\) su un'istanza \(I\) di valore ottimo \(z(I)\):
Il rapporto di prestazione nel caso peggiore è l'estremo superiore del rapporto di prestazione (A1) su tutte le istanze:
Esercizio 34.1: Rapporti di prestazione ed errori (1)
Un algoritmo euristico \(\mathscr{A}\) per un problema di minimo e un algoritmo euristico \(\mathscr{B}\) per un problema di massimo danno i seguenti valori su alcune istanze:
Domande
-
Calcolare il rapporto di prestazione, l'errore additivo e l'errore relativo di \(\mathscr{A}\) sulle sue cinque istanze.
-
Fare lo stesso per \(\mathscr{B}\) sulle sue tre istanze.
-
Usando solo questi dati, quale delle costanti \(\alpha=\frac{7}{5}\) e \(\alpha=\frac{3}{2}\) può essere una garanzia di prestazione relativa di \(\mathscr{A}\)? Che cosa servirebbe per dimostrare che \(\mathscr{A}\) è un algoritmo di \(\frac{3}{2}\)-approssimazione?
-
Supporre che sia dimostrato che \(\mathscr{A}\) è un algoritmo di \(\frac{3}{2}\)-approssimazione. La garanzia è tight? Dare un lower bound su \(r(\mathscr{A})\) e su \(r(\mathscr{B})\).
Soluzione
Usiamo le definizioni (A1)–(A4) del box all'inizio del capitolo.
-
Per un problema di minimo il rapporto è \(\frac{\mathscr{A}(I)}{z(I)}\):
istanza \(\mathscr{A}(I)\) \(z(I)\) rapporto errore additivo errore relativo \(I_1\) \(12\) \(10\) \(\frac{6}{5}\) \(2\) \(\frac{1}{5}\) \(I_2\) \(9\) \(9\) \(1\) \(0\) \(0\) \(I_3\) \(15\) \(10\) \(\frac{3}{2}\) \(5\) \(\frac{1}{2}\) \(I_4\) \(20\) \(16\) \(\frac{5}{4}\) \(4\) \(\frac{1}{4}\) \(I_5\) \(7\) \(6\) \(\frac{7}{6}\) \(1\) \(\frac{1}{6}\) -
Per un problema di massimo il rapporto è \(\frac{z(I)}{\mathscr{B}(I)}\):
istanza \(\mathscr{B}(I)\) \(z(I)\) rapporto errore additivo errore relativo \(I_1\) \(30\) \(36\) \(\frac{6}{5}\) \(6\) \(\frac{1}{6}\) \(I_2\) \(25\) \(25\) \(1\) \(0\) \(0\) \(I_3\) \(16\) \(24\) \(\frac{3}{2}\) \(8\) \(\frac{1}{3}\) Tutti i rapporti sono almeno \(1\), come deve essere per soluzioni ammissibili.
-
Su \(I_3\) il rapporto è \(\frac{3}{2}>\frac{7}{5}\): \(\alpha=\frac{7}{5}\) non è una garanzia di prestazione relativa. I dati non escludono \(\alpha=\frac{3}{2}\), perché ogni rapporto è al più \(\frac{3}{2}\). Una dimostrazione deve mostrare \(\mathscr{A}(I)\le\frac{3}{2}\,z(I)\) per ogni istanza \(I\): un numero finito di esempi può solo smentire una garanzia.
-
Sì: l'istanza \(I_3\) raggiunge il rapporto \(\frac{3}{2}\), quindi nessuna costante minore è una garanzia, e \(r(\mathscr{A})=\frac{3}{2}\). Senza una dimostrazione, i dati danno solo lower bound: \(r(\mathscr{A})\ge\frac{3}{2}\) e \(r(\mathscr{B})\ge\frac{3}{2}\) (istanza \(I_3\) di \(\mathscr{B}\)).
Esercizio 34.2: Una garanzia tight per un algoritmo semplice (1)
Per \(P\|C_{\max}\) consideriamo l'algoritmo \(\mathrm{ONE}\), che assegna tutti i lavori alla macchina \(1\), così che \(\mathrm{ONE}(I)=\sum_{j\in\mathscr{J}}t_j\). Ogni istanza soddisfa \(z(I)\ge\frac{\sum_j t_j}{m}\), perché la somma degli \(m\) carichi è \(\sum_j t_j\). Consideriamo le istanze
-
\(I_1\): \(m=2\) e \(t=(7,5,4,3,3)\);
-
\(I_2\): \(m=3\) e \(t=(9,2,2,2,1)\);
-
\(I_3\): \(m=3\) e \(t=(5,5,4,4,3,3,3)\);
Domande
-
Calcolare \(\mathrm{ONE}(I)\), \(z(I)\) (per enumerazione) e il rapporto di prestazione sulle tre istanze.
-
Dimostrare che \(\mathrm{ONE}\) è un algoritmo di \(m\)-approssimazione per ogni numero fissato \(m\) di macchine.
-
Costruire, per ogni \(m\ge 2\), un'istanza su cui il rapporto è esattamente \(m\), e verificarla con \(m=4\). Che cosa si può concludere?
-
\(\mathrm{ONE}\) ha una garanzia di prestazione additiva finita? Usare l'istanza \(I_1\) con tutti i tempi di lavorazione moltiplicati per \(10\).
Soluzione
Usiamo le definizioni (A1)–(A4) del box all'inizio del capitolo.
-
istanza \(m\) \(\mathrm{ONE}(I)\) \(z(I)\) rapporto garanzia \(m\) \(I_1\) \(2\) \(22\) \(11\) \(2\) \(2\) \(I_2\) \(3\) \(16\) \(9\) \(\frac{16}{9}\) \(3\) \(I_3\) \(3\) \(27\) \(9\) \(3\) \(3\) Il rapporto non supera mai \(m\), ed è uguale a \(m\) su \(I_1\) e \(I_3\).
-
Per ogni istanza, \(z(I)\ge\frac{\sum_j t_j}{m}\) dà
\[ \frac{\mathrm{ONE}(I)}{z(I)}=\frac{\sum_j t_j}{z(I)}\le\frac{\sum_j t_j}{\frac{\sum_j t_j}{m}}=m . \] -
Prendiamo \(n=2m\) lavori di tempo \(1\). Due lavori per macchina danno \(z(I)=2\), mentre \(\mathrm{ONE}(I)=2m\): il rapporto è \(m\). Con \(m=4\): \(\mathrm{ONE}(I)=8\), \(z(I)=2\) (enumerazione) e il rapporto è \(4\). La garanzia \(m\) è tight e \(r(\mathrm{ONE})=m\).
-
Moltiplicando i tempi di \(I_1\) per \(10\) si ottiene \(t=(70,50,40,30,30)\), con \(\mathrm{ONE}(I)=220\) e \(z(I)=110\): l'errore additivo passa da \(11\) a \(110\). Moltiplicando per un qualsiasi \(K\) l'errore si moltiplica per \(K\), quindi nessuna costante \(\beta\) lo limita: \(e(\mathrm{ONE})=\infty\), mentre il rapporto resta \(2\).
Esercizio 34.3: Un algoritmo senza garanzia (1)
Per il BPP consideriamo l'algoritmo \(\mathrm{SEP}\), che mette ogni oggetto in un contenitore separato, così che \(\mathrm{SEP}(I)=n\). Consideriamo l'istanza \(I_0\) con \(c=10\) e pesi \((6,5,4,3,2)\) e, per \(k\in\Z_{\ge 2}\), le istanze \(I_k\) con \(c=k\) e \(2k\) oggetti di peso \(1\).
Domande
-
Calcolare \(\mathrm{SEP}(I_0)\), \(z(I_0)\), il rapporto di prestazione e l'errore additivo su \(I_0\).
-
Calcolare il rapporto di prestazione su \(I_k\) per \(k=3,5,10\) (usare l'enumerazione per \(k=3\)) e la sua espressione per ogni \(k\).
-
\(\mathrm{SEP}\) è un algoritmo di \(\alpha\)-approssimazione per qualche costante \(\alpha\)? Dare \(r(\mathrm{SEP})\) ed \(e(\mathrm{SEP})\).
-
Usando \(z(I)\ge 2\), mostrare che \(\frac{\mathrm{SEP}(I)}{z(I)}\le\frac{n}{2}\). Perché \(\frac{n}{2}\) non è una garanzia di prestazione relativa?
Soluzione
Usiamo le definizioni (A1)–(A4) del box all'inizio del capitolo.
-
\(\mathrm{SEP}(I_0)=5\) e \(z(I_0)=2\) (schemi \(\{1,3\}\) e \(\{2,4,5\}\)). Il rapporto è \(\frac{5}{2}\) e l'errore additivo è \(5-2=3\).
-
Due contenitori di capacità \(k\) contengono i \(2k\) oggetti unitari, e un contenitore non basta, quindi \(z(I_k)=2\):
\(k\) \(c\) \(\mathrm{SEP}(I_k)=2k\) \(z(I_k)\) rapporto \(3\) \(3\) \(6\) \(2\) \(3\) \(5\) \(5\) \(10\) \(2\) \(5\) \(10\) \(10\) \(20\) \(2\) \(10\) In generale il rapporto è \(\frac{2k}{2}=k\).
-
No: per ogni costante \(\alpha\), l'istanza \(I_k\) con \(k>\alpha\) ha rapporto \(k>\alpha\). Quindi \(r(\mathrm{SEP})=\infty\). Anche l'errore additivo su \(I_k\), pari a \(2k-2\), è illimitato: \(e(\mathrm{SEP})=\infty\).
-
Se \(z(I)\ge 2\), allora \(\frac{\mathrm{SEP}(I)}{z(I)}=\frac{n}{z(I)}\le\frac{n}{2}\). Il bound dipende dall'istanza attraverso \(n\): una garanzia di prestazione relativa deve essere un'unica costante \(\alpha\) valida per tutte le istanze.
Esercizio 34.4: Rapporto illimitato di un algoritmo greedy (1)
Per il KP consideriamo l'algoritmo \(\mathrm{GR}\): ordinare gli oggetti per efficienza \(\frac{p_j}{w_j}\) non crescente (pareggi: indice minimo) e inserire ogni oggetto, in questo ordine, se entra nella capacità residua. Consideriamo l'istanza \(I_0\) con \(c=9\), \(p=(10,7,6,4)\), \(w=(5,4,3,3)\) e, per \(M\in\Z_{\ge 3}\), le istanze \(I_M\) con \(c=M\) e due oggetti: \(p_1=2\), \(w_1=1\) e \(p_2=M\), \(w_2=M\).
Domande
-
Applicare \(\mathrm{GR}\) a \(I_0\), calcolare \(z(I_0)\) per enumerazione, il rapporto di prestazione e l'errore relativo.
-
Applicare \(\mathrm{GR}\) a \(I_M\) e calcolare \(z(I_M)\), il rapporto di prestazione e l'errore additivo per \(M=3,10,100\).
-
\(\mathrm{GR}\) è un algoritmo di \(\alpha\)-approssimazione per qualche costante \(\alpha\)? È un algoritmo di approssimazione \(\beta\)-additivo?
-
Quale proprietà delle istanze \(I_M\) fa fallire \(\mathrm{GR}\)?
Soluzione
Usiamo le definizioni (A1)–(A4) del box all'inizio del capitolo.
-
Le efficienze sono \(2\), \(\frac{7}{4}\), \(2\), \(\frac{4}{3}\): l'ordine è \((1,3,2,4)\). \(\mathrm{GR}\) inserisce gli oggetti \(1\), \(3\) e ottiene \(\mathrm{GR}(I_0)=16\). L'enumerazione dà \(z(I_0)=17\) (oggetti \(\{1,2\}\)). Il rapporto è \(\frac{17}{16}\) e l'errore relativo è \(\frac{17-16}{17}=\frac{1}{17}\).
-
L'oggetto \(1\) ha efficienza \(2\) e l'oggetto \(2\) ha efficienza \(1\): \(\mathrm{GR}\) inserisce l'oggetto \(1\), e poi l'oggetto \(2\) non entra nella capacità residua \(M-1\). Quindi \(\mathrm{GR}(I_M)=2\), mentre il solo oggetto \(2\) dà \(z(I_M)=M\):
\(M\) \(\mathrm{GR}(I_M)\) \(z(I_M)\) rapporto errore additivo \(3\) \(2\) \(3\) \(\frac{3}{2}\) \(1\) \(10\) \(2\) \(10\) \(5\) \(8\) \(100\) \(2\) \(100\) \(50\) \(98\) -
Il rapporto \(\frac{M}{2}\) cresce senza limite, quindi nessuna costante \(\alpha\) va bene e \(r(\mathrm{GR})=\infty\). Anche l'errore additivo \(M-2\) è illimitato: \(e(\mathrm{GR})=\infty\).
-
L'oggetto efficiente è piccolo e blocca l'oggetto grande, il cui profitto è quasi tutto il valore ottimo: l'ordine per efficienza ignora quanto profitto porta un oggetto in termini assoluti.
Esercizio 34.5: Schemi di approssimazione (1)
Uno schema di approssimazione \(\{\mathscr{A}_\varepsilon\}_{\varepsilon\in(0,1)}\) viene eseguito su alcune istanze. La tabella riporta il tipo di problema, il parametro di accuratezza \(\varepsilon\), il valore ottimo e il valore restituito:
| caso | problema | \(\varepsilon\) | \(z(I)\) | \(\mathscr{A}_\varepsilon(I)\) |
|---|---|---|---|---|
| (1) | minimo | \(\frac{1}{10}\) | \(100\) | \(108\) |
| (2) | minimo | \(\frac{1}{10}\) | \(60\) | \(67\) |
| (3) | massimo | \(\frac{1}{5}\) | \(50\) | \(41\) |
| (4) | massimo | \(\frac{1}{5}\) | \(50\) | \(38\) |
Domande
-
Per ogni caso, calcolare l'errore relativo e stabilire se il valore è compatibile con la definizione di schema di approssimazione.
-
Tradurre \(\varepsilon=\frac{1}{4}\) in una garanzia di prestazione relativa, per un problema di minimo e per un problema di massimo. Qual è l'accuratezza?
-
Uno schema per un problema di massimo deve essere un algoritmo di \(\frac{5}{4}\)-approssimazione. Quale valore di \(\varepsilon\) serve?
-
Classificare i seguenti tempi di esecuzione di uno schema di approssimazione su istanze di dimensione \(n\): \(O(n^{1/\varepsilon})\), \(O(n^{3}/\varepsilon)\), \(O(n\,2^{1/\varepsilon})\), \(O(n^{2}/\varepsilon^{2})\), \(O(2^{n}/\varepsilon)\).
Soluzione
-
-
(1) \(\frac{108-100}{100}=\frac{2}{25}\) \(\le\) \(\frac{1}{10}\): compatibile.
-
(2) \(\frac{67-60}{60}=\frac{7}{60}\) \(>\) \(\frac{1}{10}\): non compatibile, lo schema sbaglia su questa istanza.
-
(3) \(\frac{50-41}{50}=\frac{9}{50}\) \(\le\) \(\frac{1}{5}\): compatibile.
-
(4) \(\frac{50-38}{50}=\frac{6}{25}\) \(>\) \(\frac{1}{5}\): non compatibile, lo schema sbaglia su questa istanza.
-
-
Per un problema di minimo \(\mathscr{A}_\varepsilon(I)\le(1+\varepsilon)\,z(I)\), quindi la garanzia è \(1+\frac{1}{4}=\frac{5}{4}\). Per un problema di massimo \(\mathscr{A}_\varepsilon(I)\ge(1-\varepsilon)\,z(I)\), quindi la garanzia è \(\frac{1}{1-\varepsilon}=\frac{4}{3}\). L'accuratezza è \(\frac{1}{\varepsilon}=4\).
-
Serve \(\frac{1}{1-\varepsilon}\le\frac{5}{4}\), cioè \(1-\varepsilon\ge\frac{4}{5}\) e \(\varepsilon\le\frac{1}{5}\): va bene qualunque \(\varepsilon\le\frac{1}{5}\), e \(\varepsilon=\frac{1}{5}\) è il più grande.
-
-
\(O(n^{1/\varepsilon})\): PTAS, non FPTAS.
-
\(O(n^{3}/\varepsilon)\): FPTAS.
-
\(O(n\,2^{1/\varepsilon})\): PTAS, non FPTAS.
-
\(O(n^{2}/\varepsilon^{2})\): FPTAS.
-
\(O(2^{n}/\varepsilon)\): non è un PTAS.
Un PTAS richiede un polinomio in \(n\) per ogni \(\varepsilon\) fissato; un FPTAS richiede un polinomio sia in \(n\) sia in \(\frac{1}{\varepsilon}\). I termini \(n^{1/\varepsilon}\) e \(2^{1/\varepsilon}\) non sono polinomiali in \(\frac{1}{\varepsilon}\), e \(2^n\) non è polinomiale in \(n\).
-