Approximation Algorithms
6.854 Notes #20

David Karger

Approximation Algorithms

What do you do when a problem is NP-complete?

Definitions:

Techincal assumptions we’ll often make:

NP-hardness

Approximation algorithm:

Absolute Approximations

Definition: \(k\)-abs approx if on any \(I\), have \(|A(I)-OPT(I)| \le k\)

Example: planar graph coloring.

Known only for trivial cases, where opt is bounded by a constant.

Often, can show impossible by “scaling” the problem.

Relative Approximation

Definitions:

How do we prove algorithms have relative approximations?

Greedy Algorithms

Do obvious thing at each step.

Max cut

Set cover

Vertex cover:

Graham’s rule for \(P||C_{\max}\) is a \(2-\frac1m\) approximation algorithm

Notice:

0.1 Scheduling Theory

General notation: machines \(\mid\) constraints/features \(\mid\) objective

Approximation Schemes

So far, we’ve seen various constant-factor approximations.

An approximation scheme is a family of algorithms \(A_\epsilon\) such that

But note: runtime might be awful as function of \(\epsilon\)

FPAS, Pseudopolynomial algorithms

Knapsack example.

Dynamic program for bounded integer profits

did this prove \(P=NP\)?

rounding

Wait, how do we know \(P\)?

pseudopoly gives FPAS; converse almost true

From FPAS to pseudo poly:

Enumeration

More powerful idea: \(k\)-enumeration

Scheduling any number of machines

Combine enumeration and rounding

Hardness

Relaxations

So far we’ve seen two techniques:

Can we be more clever?

TSP

intuition: SPT for \(1||\sum C_j\)

\(1 | r_j | \sum C_j\)

LP relaxations

Three steps

0.2 Vertex cover

\[\begin{aligned} &\min \sum x_i\\ x_i+x_j &\ge 1& (i,j)\in E\\ x_i&\in{0,1}\end{aligned}\]

Rounding

Even weighted (unlike greedy).

Approximation hardness:

Facility Location

Metric version, with triangle inequality.

ILP \[\begin{aligned} &\min \sum f_iy_i + \sum c_{ij}x_{ij}\\ x_{ij} &\le y_i\\ \sum_i x_{ij} &\ge 1\end{aligned}\]

Step 1: filtering

Step 2: Facility opening: intuition

Step 2: Facility opening: details

Combine:

Further research progress has yielded

MAX SAT

Define.

random setting

LP \[\begin{aligned} \max &&\sum z_j\\ \sum_{i \in C_j^+} y_i + \sum_{i \in C_j^-} (1-y_1) &\ge &z_j\end{aligned}\]

Analysis

LP good for small clauses, random for large.