Algoritmo di approssimazione: differenze tra le versioni

Versione delle 17:49, 11 mar 2017

Versione delle 12:39, 23 ott 2018

Riga 56:

Ormai ci sono parecchie tecniche standard che si usano per progettare un algoritmo di approssimazione. Queste comprendono le seguenti.

# [[Algoritmo greedy]]

# [[Ricerca locale (ottimizzazione)|Ricerca locale]]

# Enumerazione e [[programmazione dinamica]]

# Risolvere un rilassamento della [[programmazione convessa]] per ottenere una soluzione frazionaria. Poi convertire questa soluzione frazionaria in una soluzione fattibile mediante qualche arrotondamento appropriato. I rilassamenti più conosciuti includono i seguenti.