What is an approximation algorithm?

An approximation algorithm is an approach used for dealing with non-deterministic polynomial-time complete (NP-complete) for an optimization problem. This approach does not necessarily produce the best solution. However, it tries to come as close as possible to the optimal value within polynomial time.

Furthermore, most optimization problems cannot be solved directly in polynomial time. Hence, the approximation algorithm tries to learn how closely the approximate optimal solutions for these problems can be identified under polynomial time.

NP-complete

In the computational theory, a problem is called NP-complete when:

• It is a problem in which the solution's correctness can be proved quickly and the brute-force search algorithm can find a solution to the problem using all the possible solutions.
• The problem can be used to simulate other problems whose solutions' correctness can be verified quickly.

NP-complete problems have unknown status and no polynomial-time algorithm exists for such problems. However, if one NP-complete problem can be solved within polynomial time, the solution to all other problems can be obtained.

Characteristics of approximation algorithms

The characteristics of approximation algorithms are listed below:

• The algorithm guarantees execution in polynomial time even though it does not guarantee the best solution.
• The algorithm promises to pursue a highly accurate and top-quality solution.
• The algorithms are used for determining a solution near the optimal answer of the optimization problem within polynomial time.

Performance of approximation algorithms

To understand the performance of approximation algorithms, consider the following scenarios:

Scenario 1: 

Think of an optimization problem in which every solution has a cost. The aim is to identify the near-optimal solution. Based on the situation, this optimal solution may be the solution with the maximum possible cost or the solution with the least possible cost. This means that the problem will either be a minimization problem or a maximization problem.

Now, let C be the cost of the solution generated for a problem of input size n, and C* be the problem’s optimal solution. Consequently, the approximation ratio P(n) will be given as,

$max (\raisebox{1ex}{$C$}\!\left/ \!\raisebox{-1ex}{$C*$}\right.,\raisebox{1ex}{$ C*$}\!\left/ \!\raisebox{-1ex}{$C$}\right.) \le P\left(n\right)$

Scenario 2: 

If the algorithm reaches an approximation ratio P(n), the algorithm is called the P(n) approximation algorithm.

• For the maximization problems, $\raisebox{1ex}{$C^{*}$}\!\left/ \!\raisebox{-1ex}{$C$}\right. \le P\left(n\right)$ means the factor through which the optimal solution is obtained is more than the actual solution.
• For the minimization problems, $\raisebox{1ex}{$C$}\!\left/ \!\raisebox{-1ex}{$C^{*} \le P\left(n\right)$}\right.$ means the factor through which the actual solution is obtained is more than the optimal solution.

Examples of approximation algorithm

The examples of an approximation algorithm include:

• The vertex-cover problem
• Traveling salesman problem (TSP)
• The set covering problem

Vertex cover problem

A vertex cover of a graph is the set of vertices having a minimum of one endpoint for every edge in the graph. In this problem, the optimization problem is about selecting the least number of vertices that cover all the edges in the graph.

The vertex cover problem is NP-Complete because the polynomial-time solution for identifying the minimum vertex cover is unknown. However, there exist approximate polynomial-time algorithms for solving the vertex cover problem.

Below is the approximate algorithm for the vertex cover problem:

• Declare the vertex cover set as empty.
• Name the set of all the edges of graph E.
• While E is not empty, do the following:
  • Select an arbitrary edge (u, v) from the set, add its constituent nodes, u and v, to the vertex cover set.
  • Remove all the edges having u or v as a part of them from the set E.
  • Return the final answer (the vertex cover set) once the set E gets empty.

Traveling-salesman problem

The traveling-salesman problem is used for finding the shortest route between a set of cities or the locations that the salesman has to visit. The optimization problem in the traveling salesman problem is the one where the salesman has to choose the path that has the least cost so that the cost of traveling and distance traveled are the lowest. The traveling salesman problem is NP-complete as no polynomial-time solution is known for the problem.

Here is the approximate approach used for solving the traveling salesman problem:

• Select any city, say city 1, as the start and endpoint for the salesman. This means that the route will be cyclic.
• Now, create all possible permutations of the cities (n-1)!
• Determine the cost of every permutation.
• Track the minimum cost permutation.
• Return the permutation having the least value.

The set covering problem

For a given universal set U of n elements and a collection of subsets S, the set cover problem aims to find the minimum cost subcollection of S, which consists of all elements of the set U. The set covering problem is one of Karp's 21 NP-complete problems.

The set cover problem is NP-complete since no polynomial time solution for this problem has been determined. However, a greedy approximate algorithm for the set cover problem exists, which is as mentioned below:

Consider:

U = universal set of elements

{S₁, S₂, S₃, …, S_m}  = collection of subsets of U

Cost(S₁), Cost(S₂), …, Cost(S_m) = cost of subsets

Now, the algorithm will be:

Initialize the set of elements as V.

Until V is not equal to U, do the following:

• Search for the smallest set S_v in {S₁, S₂, S₃, …, S_m} having the least cost-effectiveness. It means the ratio of Cost(S_v) and the number of the newly added element is the lowest.
• Add the elements selected from the above S_v to V. It means performing a union operation between V and S_v.

Context and Applications

The topic approximation algorithm is a significant concept in the theory of computation and data structure and algorithms. The concept is studied in undergraduate and postgraduate courses like:

• Bachelors of Science in Computer Science
• Masters of Science in Computer Science
• Bachelors of Technology in Computer Science Engineering
• Masters of Technology in Computer Science Engineering
• Masters of Science in Applied Science

Practice Problems

Q1. Which algorithm aims to find the shortest distance between two cities?

1. Traveling-salesman problem
2. 2-approximation combinatorial optimization
3. K-median lecture notes technique 
4. Randomized technique 

Answer: Option a

Explanation: The traveling-salesman problem aims to find the shortest distance between two cities or locations that the salesman has to visit.

Q2. What kind of solution does the approximation algorithm provide?

1. Best
2. Worst
3. Average
4. None of the above

Answer: Option d

Explanation: The approximation algorithm does not provide the best solution always. It tries to come as near as possible to the optimal value in polynomial time. So, all the options are incorrect.

Q3. Which of these is an example of an approximation algorithm?

1. Inapproximability method rounding 
2. Vertex cover problem
3. Triangle inequality method
4. Facility location rounding 

Answer: Option b

Explanation: The examples of approximation algorithms include vertex cover problem, set covering problem, and traveling-salesman problem.

Q4. When can the solution to all other problems in NP-complete be obtained?

1. If the solution to one problem is obtained
2. If the rounding method is slow
3. If triangle inequality is zero
4. Never

Answer: Option a

Explanation: When the solution to one NP-complete problem is obtained in polynomial time, the solution to all other problems can be obtained.

Q5. What is the full form of NP-complete?

1. No performance guarantee complete
2. Non-deterministic performance-time complete
3. Non-deterministic polynomial-time complete
4. Non-polynomial-time approximation scheme complete

Answer: Option c

Explanation: The term NP-complete stands for non-deterministic polynomial-time complete.

Common Mistakes

The topics, set cover problem and vertex-cover problems sound similar, so most students consider these concepts the same. However, it is worth noting that they are different concepts. So, students need to know their differences to avoid making mistakes in these concepts.

Related Concepts

• NP-hard problems
• Polynomial-time approximation scheme (PTAS)
• Dynamic programming
• Linear search
• Linear programming
• Primal-dual methods
• Randomized approximation algorithm