Algoritmi di approssimazione Parte I

Descrizione

Algoritmi di approssimazione, parte I.

Con quale efficienza è possibile impacchettare gli oggetti in un numero minimo di scatole? In che modo è possibile raggruppare i nodi in modo da separare in modo economico una rete in componenti attorno ad alcuni centri? Questi sono esempi di problemi di ottimizzazione combinatoria NP-hard. Molto probabilmente è impossibile risolvere tali problemi in modo efficiente, quindi il nostro obiettivo è fornire una soluzione approssimativa che può essere calcolata in tempo polinomiale e che allo stesso tempo abbia garanzie dimostrabili sul suo costo relativamente all'ottimale.

Questo corso presuppone la conoscenza di un corso di Algoritmi standard universitario e sottolinea in particolare gli algoritmi che possono essere progettati utilizzando la programmazione lineare, una tecnica preferita e di incredibile successo in questo settore. Seguendo questo corso, sarai esposto a una serie di problemi alla base dell'informatica teorica e a potenti tecniche di progettazione e analisi. Al termine, sarai in grado di riconoscere, di fronte a un nuovo problema di ottimizzazione combinatoria, se è vicino a uno dei pochi problemi di base noti e sarai in grado di progettare rilassamenti di programmazione lineari e utilizzare arrotondamenti randomizzati per tentare di risolvere il tuo proprio problema. Il contenuto del corso e in particolare i compiti a casa sono di natura teorica senza compiti di programmazione.

Questo è il primo di un corso in due parti sugli algoritmi di approssimazione.