Problemi di Occupancy e Balanced Allocation

In questa tesina si descrive e si analizza il processo Balls and Bins per ottenere delle approssimazioni per il carico massimo e il numero di scatole vuote, anche nei casi in cui il numero di palline non coincide con il numero di scatole. Si cita inoltre una variante che permette di ottenere una distribuzione del carico più bilanciata. Infine si discutono alcune applicazioni del processo in algoritmi e strutture dati: bucket sort, hash table e Bloom filters