근사 알고리즘

편집 역사 토론
최적설계 수치해석 마지막 수정: 2026-08-03 04:24:36

1. 개요[편집]

최적해는 못 구한다. 그런데 “얼마나 못 구했는지”는 증명할 수 있다. 그게 근사 알고리즘이다.

근사 알고리즘(approximation algorithm)은 NP-난해 최적화 문제에 대해 다항 시간에 실행되면서, 출력한 해가 최적해로부터 증명된 배수 이내임을 보장하는 알고리즘이다. 핵심은 “빠르다”가 아니라 “보장한다”이다. 담금질 모사나 유전 알고리즘 같은 메타휴리스틱도 다항 시간에 그럴듯한 해를 주지만, 그 해가 최적해의 100배인지 1.01배인지는 아무도 모른다. 근사 알고리즘은 그 배수에 상수를 박아 넣는다.

분지한정법이 “시간을 쓰면 최적성을 증명한다”는 노선이라면, 근사 알고리즘은 “시간을 고정하고 최적성의 손실을 증명한다”는 반대편 노선이다. 조합 최적화 이론의 절반은 이 두 노선 위에 서 있다.

2. 근사비[편집]

최소화 문제에서 알고리즘 AA 의 근사비(approximation ratio) ρ≥1\rho \ge 1 은 모든 입력 II 에 대해

A(I)≤ρ⋅OPT(I)A(I) \le \rho \cdot \mathrm{OPT}(I)

를 만족하는 최소의 상수다. 최대화 문제에서는 부등호가 뒤집혀 A(I)≥ρ⋅OPT(I)A(I) \ge \rho \cdot \mathrm{OPT}(I) 이고 이때 ρ≤1\rho \le 1 이다.1 최악의 경우(worst case)에 대한 보장이지 평균적 성능이 아니라는 점이 중요하다. 실제로 2-근사 알고리즘이 현실 입력에서는 1.01배쯤에서 노는 경우가 흔하다.

근사 가능성의 정도에 따라 문제들은 다음 계층으로 갈린다.

계층정의대표 문제
FPTAS(1+ε)(1+\varepsilon) 근사를 nn 과 1/ε1/\varepsilon 의 다항 시간에배낭 문제
PTAS고정 ε\varepsilon 마다 다항 시간, 1/ε1/\varepsilon 에는 지수 허용유클리드 TSP
APX어떤 상수 ρ\rho 로 근사 가능정점 커버, 메트릭 TSP
로그 근사Θ(log⁡n)\Theta(\log n) 이 최선집합 커버
근사 불가상수 근사가 NP-난해일반 TSP, 최대 클리크

계층은 진짜로 포함 관계다. FPTAS ⊆ PTAS ⊆ APX 이고, P ≠ NP 라면 각 포함은 엄밀하다.

3. 배낭 문제의 FPTAS[편집]

FPTAS의 교과서 예제. 배낭 문제는 동적 계획법으로 값 축을 따라 O(n2vmax⁡)O(n^2 v_{\max}) 에 정확히 풀린다. 이건 다항 시간이 아니라 의사다항(pseudo-polynomial) 시간이다 — 값 vmax⁡v_{\max} 를 입력 길이가 아니라 크기로 재고 있기 때문.

여기서 값을 통째로 스케일링해 버린다. K=εvmax⁡/nK = \varepsilon v_{\max}/n 로 두고

vi′=⌊viK⌋v_i' = \left\lfloor \frac{v_i}{K} \right\rfloor

로 반올림한 뒤 같은 DP를 돌린다. 값의 자릿수가 줄었으니 표가 작아져 O(n3/ε)O(n^3/\varepsilon) 이 되고, 아이템마다 잃는 값이 최대 KK 이므로 총 손실은 nK=εvmax⁡≤ε⋅OPTnK = \varepsilon v_{\max} \le \varepsilon \cdot \mathrm{OPT} 이하다. 결국 (1−ε)(1-\varepsilon) 근사.2 “정밀도를 버려서 다항성을 산다”는 이 수법은 수치해석의 절단오차 관리와 정확히 같은 정신이다.

참고로 강한 NP-난해(strongly NP-hard) 문제는 P = NP 가 아닌 한 FPTAS를 가질 수 없다. 값을 스케일링해도 여전히 어려운 부분이 남기 때문. 배낭이 FPTAS를 갖는 건 배낭이 약한 의미로만 어렵다는 증거다.

4. 정점 커버와 LP 반올림[편집]

정점 커버(모든 간선을 덮는 최소 정점 집합)의 2-근사는 두 줄이면 끝난다. 극대 매칭을 하나 잡고 그 끝점을 전부 넣는다. 매칭의 각 간선은 최소 한 끝점이 최적해에 있어야 하므로 OPT≥∣M∣\mathrm{OPT} \ge |M| 이고, 우리가 낸 답은 2∣M∣2|M| 이다.

더 일반적인 도구가 LP 반올림이다. 정수계획법 정식화 min⁡∑vxv\min \sum_v x_v subject to xu+xv≥1x_u + x_v \ge 1 의 선형계획법 완화를 풀면, 정점 커버 LP는 반정수성(half-integrality)을 가져 모든 꼭짓점 해가 {0,1/2,1}\{0, 1/2, 1\} 값만 갖는다. xv≥1/2x_v \ge 1/2 인 정점을 전부 채택하면 비용이 많아야 2배 — 다시 2-근사다.

여기서 정수 격차(integrality gap)라는 개념이 나온다. LP 최적값과 IP 최적값의 최악 비율이다. 정점 커버 LP의 정수 격차는 정확히 2이므로(모든 xv=1/2x_v = 1/2 가 실행가능한 완전 그래프), LP 경계만 쓰는 어떤 알고리즘도 2보다 잘할 수 없다. 정수 격차는 알고리즘의 한계가 아니라 그 알고리즘이 쓰는 경계의 한계를 재는 자다. 같은 이유로 절단평면법으로 유효 부등식을 추가해 격차를 줄이는 것이 곧 근사비 개선으로 이어진다.

5. 집합 커버와 그리디의 최적성[편집]

집합 커버는 ln⁡n\ln n 벽에 부딪히는 대표 문제다. 남은 원소를 가장 많이 덮는 집합을 매번 고르는 그리디가 Hn=1+1/2+⋯+1/n≤ln⁡n+1H_n = 1 + 1/2 + \dots + 1/n \le \ln n + 1 근사임은 1970년대에 이미 알려졌다.

놀라운 건 이게 개선 불가라는 쪽이다. 파이게(Feige, 1998)가 준다항 시간 가정 하에 (1−o(1))ln⁡n(1-o(1))\ln n 보다 나은 근사가 불가능함을 보였고, 디누르와 스토이러(Dinur–Steurer, 2014)가 병렬 반복(parallel repetition)의 개선으로 P ≠ NP 만 가정해도 (1−ε)ln⁡n(1-\varepsilon)\ln n 근사가 불가능함을 확립했다.3 즉 40년 된 그리디 세 줄이, 상수 인자를 빼면 인류가 도달할 수 있는 최선이다.

6. TSP — 3/2가 45년간 버틴 이야기[편집]

삼각 부등식을 만족하는 메트릭 외판원 문제에서는 최소 신장 트리를 두 번 도는 2-근사가 쉽게 나온다. 크리스토피디스(1976)와 세르디유코프(1978)가 독립적으로 개선한 3/2-근사는 MST에 홀수 차수 정점들만 모아 최소 완전 매칭을 붙여 오일러 회로를 만든 뒤 지름길을 낸다. 매칭 비용이 최적 투어의 절반 이하라는 관찰이 전부다.

이 3/2는 2020년까지 깨지지 않았다. 칼린·클라인·오베이스 가란(Karlin–Klein–Oveis Gharan, 2020)이 최대 엔트로피 분포로 신장 트리를 무작위 추출하는 방식으로 3/2−ε3/2 - \varepsilon 을 달성했는데, 그 ε\varepsilon 이 대략 10−3610^{-36} 수준이다.4 실용적 개선이 아니라 “3/2가 벽이 아니다”라는 사실 자체가 결과다. 참고로 메트릭 TSP는 123/122 보다 잘 근사하는 것이 NP-난해이고, 서브투어 제거 LP의 정수 격차는 4/3 로 추측되지만 아직 미해결이다.

반면 일반 TSP(삼각 부등식 없음)는 임의의 상수 ρ\rho 에 대해 ρ\rho-근사가 NP-난해다. 해밀턴 회로 문제의 간선 가중치를 1과 ρn\rho n 으로 두면 상수 근사 알고리즘이 해밀턴 회로의 존재 여부를 판정해 버리기 때문. 근사 알고리즘조차 없는 문제가 실재한다는 것을 보여주는 가장 깔끔한 환원이다.

7. PCP 정리와 근사 어려움[편집]

“근사도 어렵다”는 명제를 증명하는 기계가 PCP 정리(1992, Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy)다. NP의 모든 언어가 O(log⁡n)O(\log n) 개의 무작위 비트와 상수 개의 질의만으로 검증 가능하다는 이 정리는, NP-완전 문제를 “완전히 만족 가능” 대 “0.99 이상은 절대 못 채움” 두 경우로 벌려 놓는 갭 생성기로 쓰인다. 이 갭을 NP-완전 문제로 환원하면 곧바로 근사 하한이 나온다. 하스타드(1997)의 MAX-3SAT 7/8+ε7/8 + \varepsilon 근사 불가능성이 대표작이며, 무작위 배정이 정확히 7/8을 주므로 이 경우 동전 던지기가 최적 알고리즘이라는 결론이 된다. 반대편에서는 괴만스-윌리엄슨의 MAX-CUT 0.878-근사가 반정부호 계획법 완화의 위력을 보여줬고, 이 0.878 역시 유일 게임 추측 하에서 최적이다.

8. 관련 문서[편집]

9. Footnotes[편집]

  1. 최대화에서 ρ≤1\rho \le 1 로 쓰는 유파(0.878-근사)와 ρ≥1\rho \ge 1 로 뒤집어 쓰는 유파(1.139-근사)가 공존한다. 같은 알고리즘 이야기를 하면서 숫자가 달라 보이는 논문을 만나면 십중팔구 이 컨벤션 차이다. ↩

  2. Ibarra, O. & Kim, C. (1975)가 원형, Lawler(1979)가 다듬었다. 시간복잡도는 구현에 따라 O(n3/ε)O(n^3/\varepsilon) 또는 O(nlog⁡(1/ε)+1/ε4)O(n \log(1/\varepsilon) + 1/\varepsilon^4) 등으로 개선된 판본이 여럿 있다. ↩

  3. Dinur, I. & Steurer, D. (2014). “Analytical approach to parallel repetition”, STOC 2014. 가정이 “준다항 시간 알고리즘 없음”에서 “P ≠ NP”로 내려온 것이 이 결과의 핵심 가치다. 조건이 약할수록 정리는 강해진다. ↩

  4. 논문 자체가 ε\varepsilon 을 명시적으로 계산하진 않았고, 후속 정리에서 10−3610^{-36} 언저리로 추정됐다. 실용성 0에 수렴하지만 40년 넘게 아무도 못 넘던 벽에 금을 낸 값이라 2020년 최고의 결과로 꼽힌다. ↩