다중 방문수 TSP

Question

다음 문제에 대해 가능한 접근법을 제안하십시오. 두 vertex i 어커런스 사이의 거리 (모서리 가중치의 합)가 Di 이하가되도록 그래프 vertges를 통해 경로를 찾으십시오. 분명히 무한하기 때문에이 경로에 대해 생성기를 갖고 싶습니다.

Answer 1

그래프가 삼각형 부등식을 만족하면 christofides 알고리즘은 최적의 2/3 이내에 있음을 보장합니다.