핵심 인사이트

  1. NP-하드 문제의 근사 알고리즘은 "완벽하지 않지만 보장된 품질"을 빠르게 계산 — ρ-근사(Approximation Ratio) 알고리즘은 최적해의 ρ배 이하(최소화) 또는 이상(최대화)을 다항 시간에 보장하며, 이론적 최적 추구보다 실용적 접근이다.
  2. 대표 근사 알고리즘과 보장 — 버텍스 커버: 2-근사, TSP(삼각 부등식): 1.5-근사(Christofides), 집합 커버: O(log n)-근사, 배낭: FPTAS(임의 ε 근사), 2-SAT: 다항 시간 정확해.
  3. 근사 불가능성(Inapproximability)도 중요 — 집합 커버는 O(log n)보다 나은 근사가 P≠NP 가정 하에 불가능하며, Clique는 n^(1-ε) 근사도 불가능(ZPP≠NP). 근사 한계도 이론적으로 정의된다.

Ⅰ. 근사 알고리즘 기초

근사 알고리즘 (Approximation Algorithm):

목적:
  NP-하드 문제에서 다항 시간 + 품질 보장
  완벽한 최적해 대신 "충분히 좋은 해"

근사 비율 (Approximation Ratio):
  최소화 문제: ρ = A(I) / OPT(I) ≤ ρ
  최대화 문제: ρ = OPT(I) / A(I) ≤ ρ
  
  A(I): 알고리즘 출력값
  OPT(I): 최적해 값
  
  ρ=1: 완벽 최적해 (=정확 알고리즘)
  ρ=2: 최적의 2배 이하 (최소화) → "2-근사"
  ρ=1.5: 최적의 1.5배 → TSP Christofides

근사 스키마:
  PTAS (Polynomial-Time Approximation Scheme):
    임의 ε > 0에 대해 (1+ε)-근사
    시간: poly(n)이지만 ε에 지수적
    
  FPTAS (Fully PTAS):
    시간: poly(n, 1/ε)
    배낭 문제 FPTAS가 대표적

한계 (Inapproximability):
  모든 NP-하드 문제에 좋은 근사 존재 X
  Clique: n^(1-ε) 근사 불가 (ZPP≠NP)
  → 근사 자체가 NP-하드인 경우

📢 섹션 요약 비유: 근사 알고리즘은 "충분히 좋은 답" — 완벽한 답(최적해)은 너무 오래 걸리므로, "최적의 1.5배 이내"를 빠르게! 1.5배 이내 보장이 근사 알고리즘의 가치.

Ⅱ. 버텍스 커버 2-근사

버텍스 커버 (Vertex Cover):
  그래프 G=(V,E)에서 모든 에지를 커버하는 최소 정점 집합
  = NP-완전

2-근사 알고리즘:
  아이디어: 임의 에지 선택 → 양 끝점 추가 → 반복
  
  알고리즘:
  C = {}
  while E는 비어있지 않음:
    임의 에지 (u,v) 선택
    C = C ∪ {u, v}
    u, v에 인접한 모든 에지 제거
  return C
  
  예시:
  그래프: 1-2, 2-3, 3-4, 4-5
  에지 (1,2) 선택 → {1,2} 추가
  에지 (3,4) 선택 → {3,4} 추가
  에지 5에 연결된 것 → {5} or 에지 (4,5) 커버됨
  → C = {1,2,3,4}
  
  최적해: {2,4} (크기 2)
  알고리즘: 크기 4 ≤ 2 × 최적(2) ✓ 2-근사!

증명:
  선택한 에지들 = 매칭(공유 정점 없음)
  → 매칭 크기 = k
  → 알고리즘: 2k 정점
  → 최적: ≥ k (각 에지 최소 1개 정점 필요)
  → 2k / k = 2 → 2-근사 증명

시간 복잡도: O(V+E)

📢 섹션 요약 비유: 버텍스 커버 2-근사는 에지 짝 잡기 — 도로(에지) 감시에 필요한 최소 초소(정점). 무작위 도로 선택 후 양 끝 초소 세우면 최적의 2배 이내!

Ⅲ. 집합 커버 로그 근사

집합 커버 (Set Cover):
  전체 집합 U, 부분집합들 S_1, ..., S_m
  U를 커버하는 최소 부분집합 선택
  = NP-완전

그리디 알고리즘:
  아이디어: 매 단계 가장 많은 원소를 커버하는 집합 선택
  
  알고리즘:
  C = {} (선택된 집합)
  R = U (남은 원소)
  while R ≠ {}:
    S_i = R와의 교집합이 최대인 집합
    C = C ∪ {S_i}
    R = R - S_i
  return C

근사 비율:
  H_n = 1 + 1/2 + 1/3 + ... + 1/n ≈ ln(n)
  
  → O(log |U|) 근사 보장
  
  예: |U|=100 → 최적 k개, 그리디 ≤ k × ln(100) ≈ 4.6k

불가능 결과:
  (1-ε) × ln(n) 보다 좋은 근사는
  P≠NP 가정 하에 불가능 (Feige 1998)
  → ln(n) 근사가 사실상 최선

적용:
  네트워크 감시 (모든 링크 커버)
  유전체 분석 (탐침 선택)
  광고 노출 최적화
  서비스 배치 최적화

📢 섹션 요약 비유: 집합 커버 그리디는 최대 할인 선택 — 매 번 가장 많은 물건(원소)을 커버하는 할인 쿠폰(집합) 선택. log(n)배 이내 최적. 이보다 좋은 전략은 이론상 불가!

Ⅳ. TSP 1.5-근사 (Christofides)

TSP (여행하는 외판원 문제):
  n개 도시 모두 방문하는 최소 비용 순환 경로
  = NP-하드

Christofides 알고리즘 (1976, 삼각 부등식 가정):
  
  1. MST (최소 신장 트리) 계산
  2. MST에서 홀수 차수 정점 집합 O 추출
  3. O에서 최소 완전 매칭 M 계산
  4. MST + M 합친 오일러 그래프
  5. 오일러 순회 찾기
  6. 단축 (방문했던 도시 건너뛰기)

근사 비율: 1.5

증명 (개략):
  MST 비용 ≤ OPT (최적 경로에서 에지 하나 제거 = 신장 트리)
  최소 완전 매칭 ≤ OPT/2 (삼각 부등식 + 홀수 정점쌍)
  → Christofides: MST + 매칭 ≤ 1.5 × OPT

최근 개선 (2020):
  Karlin-Klein-Gharan: (1.5-ε)-근사 증명
  46년 만의 개선!
  
  하지만 엄청나게 복잡한 알고리즘
  실용성은 낮음

주의:
  삼각 부등식 없는 일반 TSP:
  P≠NP 가정 하에 임의 상수 근사 불가
  
일반 근사:
  2-opt, 3-opt: 로컬 서치 휴리스틱
  LKH (Lin-Kernighan-Helsgott): 실용 최고 품질

📢 섹션 요약 비유: Christofides는 최적 근처 여행 계획 — MST(최저비용 연결)에 홀수 도시 연결(매칭) 추가. 최적 경로의 1.5배 이내 보장. 46년간 최고 이론 기록!

Ⅴ. 실무 시나리오 — 물류 최적화

택배 회사 배송 경로 최적화:

문제:
  배송 드라이버 1명, 도시 100개
  하루 모든 배송지 방문 최소 이동 거리
  = TSP 변형

현실적 접근:

1. 거리 행렬 준비:
   100 × 100 = 10,000개 거리 (Google Maps API)

2. Christofides 1.5-근사:
   정확한 최적 보장
   하지만 최소 완전 매칭 계산 복잡
   
3. 실용 선택 — LKH (Lin-Kernighan):
   100개 도시: 밀리초~초
   품질: 최적과 0.1~0.5% 차이
   → 이론 보장은 없지만 실용 최고

4. 시뮬레이티드 어닐링 (SA):
   랜덤 탐색 + 확률적 수용
   글로벌 최적 탐색
   100개: 수초~수십초

5. 유전 알고리즘 (GA):
   복수 경로 진화
   병렬화 가능

결과 비교 (100개 도시):
  무작위 경로: 100% (기준)
  최근접이웃 그리디: ~25% 단축
  2-opt: ~15% 추가 단축
  Christofides: 이론 1.5× OPT 보장
  LKH: 실용 최고 (~0.3% OPT 차이)
  
비용 효과:
  배송 경로 최적화 10% 단축
  드라이버 일 평균 이동: 200km → 180km
  연료 비용 10% 절감 = 수천만원/년

📢 섹션 요약 비유: 물류 TSP는 우편배달부 퍼즐 — 100군데 집을 최단 거리로 돌기. Christofides는 이론 보장, LKH는 실용 최선. 1%만 줄여도 수천만원 절감!

📌 관련 개념 맵

NP 근사 알고리즘
+-- 근사 비율 (ρ)
|   +-- 2-근사: 버텍스 커버
|   +-- 1.5-근사: TSP Christofides
|   +-- O(log n): 집합 커버
+-- 근사 스키마
|   +-- PTAS
|   +-- FPTAS (배낭)
+-- 불가능성
|   +-- 집합 커버: ln(n) 이상 개선 불가
|   +-- Clique: 다항 근사 불가
+-- 실용 휴리스틱
    +-- LKH, 2-opt, 3-opt
    +-- 유전 알고리즘, SA

📈 관련 키워드 및 발전 흐름도

[초기 근사 연구 (1970s)]
버텍스 커버 2-근사
집합 커버 그리디 ln(n)
Christofides 1.5-근사 TSP
      |
      v
[PCP 정리 (1992)]
근사 불가능성 이론 정립
집합 커버 ln(n) 최선 증명
      |
      v
[FPTAS 성숙 (1990s~)]
배낭 FPTAS 체계화
실용 근사 알고리즘 폭발적 발전
      |
      v
[현재: 딥러닝 + 근사]
Graph Neural Network + TSP
강화학습 기반 경로 최적화
TSP Christofides 1.5→(1.5-ε) (2020)

👶 어린이를 위한 3줄 비유 설명

  1. 근사 알고리즘은 "충분히 좋은 답" — 완벽한 최단 경로 찾기에 수백 년 걸리면, "최단의 1.5배 이내" 경로를 빠르게 찾아요!
  2. 버텍스 커버 2-근사는 도로 감시 — 무작위 도로 선택 후 양 끝에 초소 세우면 최적의 2배 이내. 간단하지만 보장 있어요!
  3. 집합 커버는 쿠폰 선택 — 매번 가장 많이 커버하는 쿠폰(집합) 선택. log(n)배 이내 최적, 이보다 좋은 방법은 수학적으로 불가능!