Algoritmi di approssimazione Parte II

Descrizione

Algoritmi di approssimazione, parte 2

Questa è la continuazione degli algoritmi di approssimazione, parte 1. Qui apprenderai la dualità di programmazione lineare applicata alla progettazione di alcuni algoritmi di approssimazione e la programmazione semidefinita applicata a Maxcut.

Prendendo le due parti di 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 sono di natura teorica senza compiti di programmazione.

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