Dimostrare che un problema di ottimizzazione è NP-difficile non chiude la questione: le istanze vanno risolte comunque. Una delle risposte più solide offerte dalla teoria è l'algoritmo di approssimazione, che gira in tempo polinomiale e restituisce una soluzione non necessariamente ottima, ma con una garanzia dimostrata sulla distanza dall'ottimo. A differenza di un'euristica qualsiasi, la garanzia vale su ogni istanza, anche la peggiore.
Il rapporto di approssimazione
Per un problema di minimizzazione, un algoritmo è una ρ-approssimazione se per ogni istanza restituisce una soluzione di costo al più ρ volte il costo ottimo, con ρ ≥ 1. Per un problema di massimizzazione, la soluzione deve valere almeno l'ottimo diviso ρ (o, in un'altra convenzione diffusa, almeno ρ volte l'ottimo con ρ ≤ 1).
La difficoltà concettuale è evidente: non conosciamo l'ottimo, perché calcolarlo è NP-difficile. La tecnica standard consiste nel trovare un limite inferiore all'ottimo, facile da calcolare, e nel confrontare la soluzione con quel limite.
Esempio 1: copertura di vertici, rapporto 2
Il problema: trovare il più piccolo insieme di nodi che tocchi ogni arco di un grafo.
L'algoritmo:
- finché resta un arco (u, v) non coperto, aggiungi entrambi u e v alla soluzione;
- rimuovi tutti gli archi che toccano u o v.
Gli archi scelti al passo 1 non condividono estremi: formano un abbinamento (matching). Sia M questo insieme di archi.
- La soluzione ha esattamente 2|M| nodi.
- Ogni copertura, anche quella ottima, deve contenere almeno un estremo di ciascun arco di M, e questi estremi sono tutti distinti. Quindi l'ottimo vale almeno |M|.
Ne segue: soluzione ≤ 2 × ottimo. Il limite inferiore è la dimensione dell'abbinamento. È un algoritmo di poche righe con una garanzia che, sorprendentemente, è ancora oggi la migliore nota a meno di termini di ordine inferiore.
Esempio 2: commesso viaggiatore metrico
Il commesso viaggiatore chiede il giro più corto che visiti ogni città una volta. Nella versione metrica le distanze rispettano la disuguaglianza triangolare: andare direttamente da A a C non costa mai più che passare per B.
L'algoritmo in due passi:
- si calcola un albero ricoprente minimo T;
- si visita T in profondità e si elencano le città nell'ordine di prima visita, saltando quelle già viste.
Analisi:
- togliendo un arco dal giro ottimo si ottiene un albero ricoprente, quindi costo(T) ≤ ottimo;
- percorrere ogni arco di T due volte costa 2 × costo(T);
- saltare le città già viste non allunga il percorso, per la disuguaglianza triangolare.
Risultato: una 2-approssimazione. L'algoritmo di Christofides migliora il rapporto a 3/2 aggiungendo un abbinamento perfetto di costo minimo sui nodi di grado dispari dell'albero.
Senza disuguaglianza triangolare non c'è speranza
Per il commesso viaggiatore generale, se P ≠ NP, non esiste alcuna ρ-approssimazione per nessuna costante ρ. La dimostrazione è una riduzione dal problema del ciclo hamiltoniano: dato un grafo, si assegna costo 1 agli archi presenti e costo ρ·n + 1 a quelli assenti. Se esiste un ciclo hamiltoniano, il giro ottimo costa n; altrimenti costa più di ρ·n. Una ρ-approssimazione distinguerebbe i due casi e deciderebbe un problema NP-completo.
Esempio 3: lo zaino e gli schemi di approssimazione
Alcuni problemi ammettono approssimazioni arbitrariamente buone. Uno schema di approssimazione in tempo polinomiale (PTAS) è una famiglia di algoritmi che, per ogni ε > 0, dà una (1 + ε)-approssimazione in tempo polinomiale in n, ma con dipendenza qualsiasi da ε. Se la dipendenza da 1/ε è anch'essa polinomiale si parla di FPTAS.
Lo zaino ha un FPTAS. L'idea:
- si dividono i valori degli oggetti per un fattore proporzionale a ε·V_max/n e si arrotondano per difetto;
- si risolve esattamente l'istanza arrotondata con la programmazione dinamica sui valori, ora piccoli;
- l'errore introdotto dall'arrotondamento è al più una frazione ε dell'ottimo.
Si scambia così precisione con tempo in modo controllato.
I limiti: inapprossimabilità
La teoria non dice solo che cosa si può approssimare, ma anche che cosa non si può. Lo strumento centrale è il teorema PCP, una caratterizzazione di NP in termini di dimostrazioni verificabili leggendone pochi bit a caso. Ne derivano risultati come:
| Problema | Approssimazione facile | Limite se P ≠ NP |
|---|---|---|
| MAX-3SAT | Assegnamento casuale: 7/8 delle clausole in media | Non si fa meglio di 7/8 + ε |
| Copertura di insiemi | Greedy: fattore circa ln n | Non si fa meglio di (1 − ε) ln n |
| Cricca massima | Banale: fattore n | Non si fa meglio di n^(1−ε) |
| Copertura di vertici | Abbinamento: fattore 2 | Esistono limiti costanti, ma il valore esatto è aperto |
Il caso di MAX-3SAT è notevole: un algoritmo che non pensa affatto, assegnare valori a caso, raggiunge già il limite migliore possibile.
In sintesi
- Un algoritmo di approssimazione è polinomiale e garantisce su ogni istanza una distanza limitata dall'ottimo.
- La tecnica tipica confronta la soluzione con un limite inferiore all'ottimo facile da calcolare.
- La copertura di vertici ha una 2-approssimazione; il commesso viaggiatore metrico arriva a 3/2 con Christofides.
- Senza disuguaglianza triangolare il commesso viaggiatore non è approssimabile per nessuna costante, se P ≠ NP.
- Il teorema PCP fornisce limiti di inapprossimabilità, come 7/8 per MAX-3SAT.
