Algoritmi e complessita'

* Algoritmi di approssimazione

- Classi NPO, APX, PTAS, FPTAS
- Tecniche greedy
-- Problema del bilanciamento del carico (load balancing) [A]
-- Problema della selezione dei centri (center selection) [A]
-- Inapprossimabilità del problema della selezione dei centri [C]
-- Problema della copertura di insiemi (set cover) [A]
- Tecnica di pricing
-- Problema della copertura di vertici (vertex cover) [A]
-- Problema dei cammini disgiunti (disjoint paths) [A]
- Tecniche basate sull'arrotondamento
-- Problema della copertura di vertici mediante arrotondamento [A]
- Altri esempi
-- Algoritmo di Christofides per il TSP metrico [B]
-- Inapprossimabilità del TSP [D.6]
- Schemi di approssimazione in tempo polinomiale e pienamente polinomiale
-- Un PTAS (basato sulla soluzione esaustiva ridotta) per il problema della partizione minima (minimum partition) [G]
-- Un FPTAS (basato sull'arrotondamento) per il problema dello zaino (knapsack) [C]

* Algoritmi probabilistici

- L'algoritmo di Karger per il problema del taglio minimo globale (minimum global cut) [E]
- L'algoritmo di Miller-Rabin per la primalità (senza dimostrazione) [H]
- Un algoritmo basato sull'arrotondamento aleatorio per la copertura di insiemi [D.4]
- Un algoritmo randomizzato per MaxEkSat e la sua derandomizzazione [D.3]
- Teoria della complessità di approssimazione

* Teorema PCP (senza dimostrazione) [F.3, Teorema 1]
- PCP e inapprossimabilità di MaxSat e MaxE3Sat [F.3.1]
- PCP e inapprossimabilità del problema dell'insieme indipendente (independent set) [F.4.4, Claim 13 e Claim 14]

* Strutture succinte, quasi-succinte e compatte

- Strutture succinte per rango e selezione; il "Four-Russians Trick" [D.9, escluso 9.2]
- Strutture succinte per alberi binari [D.10]
- Codifica quasi-succinta di Elias-Fano per sequenze monotone [D.11, esclusi D.11.1 e D.11.2]
- Struttura compatta per le parentesi bilanciate [D.12]
- Funzioni quasi-succinte: la tecnica MWHC [D.13]
- Hash minimali perfetti [D.13]