Approximation Algorithms

This is a polynomial-time algorithm that may not find the optimal solution, but it is never too far for optimal.

Consider any minimization or maximization problem and suppose we have algorithm A. For each problem instance I, it returns a solution with values $A(I)$.

Approximation Ratio

The approximation ration of algorithm $A$ is defined as:
Minimization problem: ${\alpha }_A=ma{x}_I\frac{A(I)}{OPT(I)}$
Maximization problem: ${\alpha }_A=mi{n}_I=\frac{A(I)}{OPT)I}$

Where $OPT(I)$ is the value of the optimal solution to instance I

for minimization problems ${\alpha }_A\ge 1$ for maximization problems ${\alpha }_A\le 1$. Since A is an approximation, it will not be optimal.

Given a problem whose search version is NP Complete, the goal is to find an algorithm A with ${\alpha }_A$ closest to 1. This needs to run in Polynomial Time.

Traveling Salesman Problem with Triangle Inequality

1. Compute a Minimum Spanning Tree of graph G
2. Duplicate each edge
3. Compute a Eulerian Cycle of the graph with duplicated edges
4. To make a tour, follow the cycle and skip any vertex you have already visited
   1. Skipping makes a shortcut by the triangle inequality
5. The length of the optimal TSP ≥ length of the MST (since a tour is a spanning tree)
   1. Since we doubled each edge and used an eulerian cycle, this is an approximation algorithm with a $\alpha =2$ at worst.
6. The runtime here is $O(|V{|}^2)$ where the bottleneck is making the MST

We can also solve Hamiltonian Paths using general TSP without the triangle inequality where we set the lengths to 1 if $(u,v)\in E$, or $n{\alpha }_A+1$ if $\{u,v\}\notin E$. An HC is found in G if it uses all edges of length 1. Otherwise, it finds a tour of length $n{\alpha }_A+n$. In this case, since A is an ${\alpha }_A$ approximation, $OPT\ge \frac{n{\alpha }_A+n}{{\alpha }_A}>n$, which means there is no HC in G.

Rsults

Unless P=NP, there is no $k$ factor approximation algorithm for the TSP for any $k\ge 1$.

So if we drop the triangle approximation, even though this is NP complete, there is no approximation.

Knapsack without Repetition

We had an $O(nW)$ time Dynamic Programming algorithm as W is exponential in input size. We can modify this to find an $O(nV)$ algorithm and then a more efficient one.

Here, $V$ is the sum of all the values. The subproblem is $K(v,j)=\{min\text{ total weight to achieve a value of v using only items from {1,...,j}}\}$. $K(v,j)=\infty$ if no such set of items exists. $K(v,j+1)$ is either just $K(v,j)$, or $K(V-V_{j+1},j)$ so we either use $j+1$ or we don’t. The smallest subproblem is $K(0,j)=0$ and $K(V,0)=\infty$. Our runtime is $O(nV)$ and our answer is $\max V$ such that $K(v,n)$ ≤ W.

The Approximation

Input: An ε > 0; a knapsack problem instance.
 
Discard any item with weight > W
 
Let v_max = max_i v_i
 
Rescale values of each item:
    v̂_i = floor(v_i n / (ε v_max))
 
Run the O(nV) dynamic programming algorithm where each item i has value v̂_i and weight w_i
 
Output the resulting choice of items

This is a $(1-ϵ)$ approximation algorithm with runtime $O(\frac{n^3}{ϵ})$. This gives us an arbitrarily good approximation.