Algoritmi di approssimazione per il problema del commesso viaggiatore

La tesi affronta il problema del commesso viaggiatore (Traveling Salesman Problem, TSP), studiando in particolare i suoi algoritmi di approssimazione, ovvero algoritmi che terminano in tempo polinomiale e restituiscono una soluzione che si discosta dalla soluzione ottima al più di un fattore alpha. Nella prima parte si vanno a definire le varie versioni del TSP e a dimostrarne l’equivalenza, per poi esporre l’algoritmo di Christofides per la versione simmetrica e l'algoritmo Cycle Cover per la versione asimmetrica. Si dimostrerà in particolare che l'algoritmo di Christofides ha fattore di approssimazione di al più 3/2. Nella seconda parte si studia il problema mediante la programmazione lineare, determinando un rilassamento del problema originario, anch’esso risolvibile in tempo polinomiale: il Subtour LP. In particolare si dimostrerà che il Subtour LP ha rapporto di integralità di al più 3/2, determinando una stretta correlazione con l'algoritmo di Christofides.