Approximation Algorithm

Approximation algorithms are designed to find near-optimal solutions to NP-hard optimization problems. They run in polynomial time and have a provable performance guarantee compared to the optimal solution.

Java example for Traveling Salesman Problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
double christofides(int[][] graph) {
  
  int[] vertices = primMST(graph); 
  List<Integer> odds = new ArrayList<>();

  for (int v: vertices) {
    if (degree(graph, v) % 2 == 1) {
      odds.add(v);
    }
  }

  int[][] complete = tsp(odds);
  int[][] solution = concat(vertices, complete);

  return cost(graph, solution);

}

// Returns cost within 1.5 times optimal

C++ example for Vertex Cover:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int vertexCover(vector<vector<int>> graph) {
  
  int cover = 0;

  while (!graph.empty()) {
    int node = pickHighestDegree(graph);
    cover++;
    removeNodeAndEdges(graph, node); 
  }

  return cover; 

} 

// Returns solution within 2 times optimal

Python example for Knapsack:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def greedyKnapsack(values, weights, capacity):

  valuePerWeight = [[v/w, w] for v, w in zip(values, weights)]
  valuePerWeight.sort(reverse=True)
  
  totalValue = 0
  frac = 0
  
  for v, w in valuePerWeight:    
    if w + frac <= capacity:
      totalValue += v
      frac += w
  
  return totalValue

# Approximates within 50% of optimal solution

Approximation algorithms trade off accuracy for efficiency. Useful when optimal solutions are infeasible to compute in practice.

An Approximation Algorithm is a type of algorithm designed to find an approximate solution to optimization problems in scenarios where finding the exact solution is computationally expensive or infeasible. The goal is to get a solution that is “good enough” and can be computed quickly. These algorithms are often used for NP-hard problems where finding an optimal solution is difficult. The quality of an approximation algorithm is usually measured by its approximation ratio, which is the ratio between the approximate solution and the optimal one.

Example Code in Java

Let’s take the example of the Traveling Salesman Problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Arrays;

public class ApproximationAlgorithm {
    public static void main(String[] args) {
        int[][] graph = { /* Your adjacency matrix here */ };
        int start = 0;
        int n = graph.length;
        boolean[] visited = new boolean[n];
        int[] path = new int[n];
        Arrays.fill(visited, false);

        path[0] = start;
        visited[start] = true;

        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            int next = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && graph[start][j] < min) {
                    min = graph[start][j];
                    next = j;
                }
            }
            start = next;
            path[i] = start;
            visited[start] = true;
        }

        System.out.println("Approximate path: " + Arrays.toString(path));
    }
}

Example Code in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<std::vector<int>> graph = { /* Your adjacency matrix here */ };
    int start = 0;
    int n = graph.size();
    std::vector<bool> visited(n, false);
    std::vector<int> path(n);

    path[0] = start;
    visited[start] = true;

    for (int i = 1; i < n; ++i) {
        int min = INT_MAX;
        int next = -1;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && graph[start][j] < min) {
                min = graph[start][j];
                next = j;
            }
        }
        start = next;
        path[i] = start;
        visited[start] = true;
    }

    // Output the approximate path
    for (auto& p : path) {
        std::cout << p << " ";
    }
    std::cout << std::endl;
}

Example Code in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
graph = []  # Your adjacency matrix here
start = 0
n = len(graph)
visited = [False] * n
path = [0] * n

path[0] = start
visited[start] = True

for i in range(1, n):
    min_val = float('inf')
    next_node = -1
    for j in range(n):
        if not visited[j] and graph[start][j] < min_val:
            min_val = graph[start][j]
            next_node = j
    start = next_node
    path[i] = start
    visited[start] = True

print("Approximate path:", path)

In these examples, we’ve used a simple greedy approach to solve the Traveling Salesman Problem. Starting from an initial city, we always choose the nearest unvisited city as our next move. This provides an approximate path but not necessarily the optimal one.