근사 알고리즘 (Approximation Algorithm)

근사 알고리즘 (Approximation Algorithm)

NP-Hard 문제에서 최적해를 보장할 수 없을 때 다항 시간 내에 최적해에 가까운 해를 찾는 알고리즘으로, 근사비(Approximation Ratio)로 해의 품질 보장

목적: NP-Hard 문제 실용적 해결, 다항 시간 보장, 해 품질 보장

특징: 다항 시간, 근사비 보장, 최적해 대비 성능 분석, 이론적 기반

근사비(Approximation Ratio)

• •최소화 문제: α = ALG/OPT ≥ 1
• •최대화 문제: α = OPT/ALG ≥ 1
• •α에 가까울수록 좋은 근사

대표 알고리즘

• •Vertex Cover: 2-근사, 임의 간선의 양 끝점 선택
• •Set Cover: ln(n)-근사, 그리디 (가장 많이 커버하는 집합 선택)
• •TSP(삼각 부등식): 2-근사(MST 기반), 1.5-근사(Christofides)
• •Bin Packing: First Fit Decreasing, 11/9 OPT + 6/9 근사
• •Knapsack: FPTAS 존재 (1+ε)-근사

PTAS vs FPTAS

• •PTAS(Polynomial-Time Approximation Scheme): 모든 ε > 0에 대해 (1+ε)-근사, 시간은 n의 다항식(ε 고정)
• •FPTAS(Fully PTAS): 시간이 n과 1/ε 모두의 다항식으로, PTAS보다 강한 조건

장점: 다항 시간, 보장된 품질, 실용적, 이론적 분석 가능

단점: 최적해 아님, 문제별 설계 필요, 근사비 증명 어려움

적용사례: 조합 최적화, 스케줄링, 클러스터링, 네트워크 설계

비교: 근사알고리즘(보장/다항) vs 휴리스틱(비보장/빠름) vs 정확알고리즘(최적/지수)

연관: NP-Hard, 그리디, 휴리스틱, 조합 최적화, 복잡도 이론