2-Approximation

Input: G = (V, E) completo, non diretto, archi pesati. $\forall e \in E \rightarrow \R+$

Output: il ciclo hamiltoniano in G di costo minimo

Il problema ha una soluzione: forza bruta che mi valuta tutti quanti i cicli.

Abbiamo un piccolo problema:

• questo problema non possiamo approssimarlo con un fattore costante di approssimazione. Non esiste una alpha costante, valore preciso, per cui valga la proprietà definita prima per andare ad approssimare il problema all’interno di una determinata finestra tra l’ottimo e alpha*ottimo. Lo possiamo andare a dimostrare come concetto di riduzione: se esistesse un algoritmo di approssimazione con fattore di approssimazione costante a meno che $P = NP$. Se fosse così andrei a risolvere il ciclo hamiltoniano in tempo polinomiale. Se butto però via alcuni dei grafi che ho in input e tengo solamente quelli con alcune proprietà riesco a fare qualcosa. Devo magari andare a tenere quelli che hanno la proprietà triangolare sul costo. Se ho 3 nodi del grafo con una funzione di costo, deve essere vero che andare direttamente da un nodo all’altro deve costare di meno o sicuramente non di più che fare il giro passando per un altro nodo. Praticamente sto dicendo C(x,y) ≤ C(x,z) + C(z,y).

Il primo algoritmo che vediamo è uno di approssimazione. L’algoritmo è pensato esattamente per questo tipo di problema (si creano sperando che non sia estremamente complessi e di costo polinomiale).

1. Si crea un MST (albero di copertura minima) $G \rightarrow T*$, supponiamo che il nostro spanning tree sia T*
2. Decidiamo di andare a raddoppiare gli alberi che abbiamo all’interno del nostro albero T*.
3. Calcoliamo il ciclo euleriano (posso passare diverse volte dai nodi, ma una sola volta dagli archi). Il ciclo euleriano potrebbe esistere come no, ma posso dare una condizione necessaria che è che il grado dei nodi siano sempre pari, perché entro ed esco dai nodi più volte. Esiste in tal caso un algoritmo in tempo polinomiale per andarlo a calcolare (il ciclo Euleriano). Possiamo andarlo a calcolare perché tutti quanti hanno grado pari visto che ho raddoppiato tutto.

Proviamo a scrivere il ciclo $E = <A, B, C, D,C,G,E,G,F,G,C,B,A>$ (controlla ma direi che vada bene come risposta).

1. A partire da E possiamo andare a calcolare un ciclo hamiltoniano H facendo shortcut. Praticamente sfrutto anche il fatto della proprietà triangolare. Vedi che nella foto prende archi che non ci sono nell’MST, ma tanto avendo il grafo orignale completo non fa niente. Che mossa assurda

1. restituisco alla fine la soluzione approssimata

Non so dove sia l’ottimo, ma devo ora cercare un modo per metterli in relazione. ~~Sono abbastanza sicuro che H sia il circuito Hamiltoniano ottimo, mentre H sia un circuito Hamiltoniano che non per forza è ottimo. Anche perché in teoria ha senso che il costo del circuito Hamiltoniano perfetto sia minore di quello di un cattivo circuito.~~*

$\frac{cost(H)}{cost(H*)} \leq 2$

H è il circuito hamiltoniano ottimo. Questa informazione è stata presa dal paper stesso di Christofides →*

Da dove andiamo a prendere questo 2??

Partiamo da quello che abbiamo usato. Il valore del costo del ciclo hamiltoniano in che relazione sta col costo del ciclo Euleriano. E’ sicuramente ≤ perché usiamo le shortcut!