A proposito di casi TSP metrico

Question

Christofides' 1,5-approssimazione ritiene grafo completo come input, e come ho capito questo è essenziale . Se il grafo di input non è completa, come posso aggiungere nuovi bordi con pesi opportuni tale che il risultante grafico completo ancora soddisfa la disuguaglianza triangolare, e, naturalmente, la soluzione TSP per il grafo completo utilizza solo bordi originali? Grazie.

Answer 1

Se i bordi non soddisfano la disuguaglianza triangolare allora il problema diventa più difficile. Nel tuo caso i bordi non hanno un peso infinito (dal momento che si desidera non usarli), quindi non ci si può aspettare l'algoritmo Christofides' essere utile in quanto tale.