NP-hard 문제의 경우 다항 시간 내에 최적해를 찾는 것이 불가능합니다. 이럴 때 근사 알고리즘(Approximation Algorithms)을 사용하는데, TSP(Traveling Salesperson Problem)나 Vertex Cover와 같은 문제에서 근사 알고리즘이 어떻게 설계될 수 있는지 설명하고, 근사 비율(Approximation Ratio)의 의미와 중요성, 그리고 이를 증명하는 방법에 대해 논하시오.

NP-hard 문제에서 최적해를 다항 시간 내에 찾기 어려울 때, 근사 알고리즘은 현실적인 대안입니다. TSP의 경우, 삼각 부등식이 성립하는 그래프에서 최소 신장 트리(MST)를 구한 후, 이를 순회하는 방식으로 2배 근사 알고리즘을 설계할 수 있습니다. Vertex Cover 문제에서는 탐욕 알고리즘이나 선형 계획 완화 기법을 활용하여 근사해를 찾습니다.

근사 비율은 알고리즘이 찾은 해의 비용이 최적해의 비용 대비 얼마나 나쁜지를 나타내는 척도입니다. 예를 들어, 근사 비율이 'c'라면, 알고리즘이 찾은 해의 비용은 최적해 비용의 최대 'c'배까지 허용된다는 의미입니다. 이는 알고리즘의 성능을 정량적으로 평가하고 보장하는 데 매우 중요합니다. 근사 비율 증명은 보통 알고리즘의 해와 최적해 사이의 관계를 수학적으로 분석하여 이루어집니다.