KAIST 전산 세미나, 2018 가을학기. 16pm. 발표자 미상.

Approximation Algorithm for Optimization Problem

Mathematical Optimization

• Input: feasible solutions 집합, objective function \(f\)
• Output: \(f(x)\)를 최대화/최소화하는 \(x\)
• Running time: \(\text{poly}(|l|)\) — \(l\)을 표현하는 비트 수

Least Square Regression

• Input: \(A \in \mathbb{R}^{m \times n}\), \(b \in \mathbb{R}^m\)
• Feasible set: \(x \in \mathbb{R}^n\)
• \(f(x) = \|Ax - b\|^2\)

Discrete Optimization (Vertex Cover)

• Input: \(G = (V, E)\)
• Feasible set: \(C \subseteq V\), \(C\)가 모든 edge를 cover
• \(f(C) = |C|\), 최소화 → NP-hard [Karp 72]

핵심 관찰

“Almost every combinatory algorithm is either NP-complete or Polynomial solvable.” — Williams 2013

→ 해결책: Approximation Algorithm — 보장을 느슨하게 완화

Approximation Algorithm 정의

Polynomial time algorithm \(A\)가 \(\alpha\)-approximation:

• (minimization) \(f(A(I)) \leq \alpha \cdot \text{OPT}(I)\)
• (maximization) \(f(A(I)) \geq \alpha \cdot \text{OPT}(I)\), \(\alpha \leq 1\)

Vertex Cover (2-approximation)

Edge 하나 고름 → 양 끝 vertex + incident edges 제거 → 반복. 이 greedy = 2-approximation.

MAX 3SAT (7/8-approximation)

• Instance: 3CNF formula on \(n\) variables
• T/F 랜덤 배정 → 각 clause 만족 확률 \(= 7/8\)

MAX CUT

• Instance: \(G = (V, E)\), \(V\)를 \(\{B, R\}\)로 색칠
• \(f\): \(B\)와 \(R\) 사이 edge 수
• Random coloring: expected \(= 0.5\)
• Semidefinite programming: \(0.878\)-approximation

PCP & Unique Games Conjecture (UGC)

• UGC: 많은 hardness 결과의 foundation
• Spectral Graph Theory — Cheeger algorithms
• Small Set Expansion [RS10]

Sparse Vector

• \(\|x\|_p = \left(\sum x_i^p\right)^{1/p}\)
• \(q > p\)이면 \(\|x\|_q / \|x\|_p\)는 \(x\)의 nonzero entry가 1개일 때 최대
• Sparsity (\(p=2\)): \(A\)의 column이 \(V\)의 orthonormal basis이면 \(\|Ax\|_2 = \|x\|_2\)