Set Cover e Bin Packing: algoritmi di approssimazione e analisi del gap additivo

Nell'ultima parte dell'ultimo secolo, in molti hanno studiato i problemi NP-Completi del Bin Packing e del Set Cover, in particolare provando a fornire delle stime superiori sull’errore che si può commettere risolvendo questi problemi con degli algoritmi di approssimazione. Lo scopo di questo lavoro sarà presentare una tale stima, per una variante particolare del secondo problema, ottenuta dall’idea di sfruttare una caratteristica chiave delle istanze di Bin Packing: poter sostituire oggetti all’interno di un contenitore con oggetti più piccoli. Questa caratteristica è molto generica e i risultati sulla variante del Set Cover così ottenuta sono applicabili a una larga scala di problemi, tra cui ovviamente molteplici varianti del Bin Packing. Nel primo capitolo descriveremo argomenti e risultati generali, che saranno per lo più già noti alla maggior parte dei lettori, nel secondo e nel terzo ci concentreremo singolarmente sui problemi del Bin Packing e del Set Cover, infine l’ultimo capitolo sarà dedicato alla variante precedentemente citata.