Scribd
Upload
4 views

Approximation Algorithm

Uploaded by

pavithra.r
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views

Approximation Algorithm

Uploaded by

pavithra.r
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Approximation Algorithm

An approximation algorithm is a strategy to find near-optimal solutions to optimization


problems, particularly those classified as NP-hard, within a reasonable amount of time. These
algorithms are useful when finding the exact solution is computationally infeasible.

Key Features

1. Efficiency:
o Approximation algorithms run in polynomial time, making them suitable for
large input sizes.
2. Approximation Ratio:
o Measures how close the approximation solution is to the optimal solution.
o If CapproxC_{\text{approx}}Capprox is the cost of the solution from the
approximation algorithm and CoptC_{\text{opt}}Copt is the cost of the
optimal solution: Approximation Ratio (R)=max⁡(CapproxCopt,CoptCapprox)\
text{Approximation Ratio (R)} = \max \left(\frac{C_{\text{approx}}}{C_{\
text{opt}}}, \frac{C_{\text{opt}}}{C_{\text{approx}}}\
right)Approximation Ratio (R)=max(CoptCapprox,CapproxCopt)

Applications

 Traveling Salesman Problem (TSP).


 Vertex Cover.
 Knapsack Problem.
 Set Cover.

Limitations of Approximation Algorithms

1. Approximation Quality:
o The solution may not be close enough to the optimal, especially for problems
with high approximation ratios.
2. Not Always Applicable:
o For some problems, finding even an approximate solution can be as hard as
finding the exact solution.
3. No Guarantee for Specific Inputs:
o Performance depends on the problem instance. Some instances might yield
poor approximations.
4. Complexity of Implementation:
o Approximation algorithms can still be intricate and difficult to implement.
5. Trade-off Between Accuracy and Efficiency:
o Higher accuracy often comes at the cost of increased computational
complexity.
Example 1: Vertex Cover

Problem:

Given a graph G=(V,E)G = (V, E)G=(V,E), find the smallest subset of vertices such that
every edge in EEE has at least one endpoint in the subset.

Approximation Algorithm:

1. Start with an empty set CCC.


2. While there are edges left in the graph:
o Pick an arbitrary edge (u,v)(u, v)(u,v).
o Add both uuu and vvv to CCC.
o Remove all edges incident to uuu and vvv.
3. Return CCC.

Analysis:

 Approximation Ratio: 222 (the solution is at most twice the optimal size).

Example:

 Graph: V={1,2,3,4},E={(1,2),(2,3),(3,4)}V = \{1, 2, 3, 4\}, E = \{(1, 2), (2, 3), (3,


4)\}V={1,2,3,4},E={(1,2),(2,3),(3,4)}.
 Approximation Solution: {2,3}\{2, 3\}{2,3} (covers all edges).
 Optimal Solution: {2,3}\{2, 3\}{2,3} (in this case, the approximation is exact).

Example 2: Traveling Salesman Problem (TSP)

Problem:

Find the shortest possible route that visits every city exactly once and returns to the starting
city.

Approximation Algorithm:

 Use Minimum Spanning Tree (MST):


1. Compute the MST of the graph.
2. Perform a preorder traversal of the MST.
3. Return the traversal as the approximate tour.

Approximation Ratio:

 For metric TSP (distances satisfy the triangle inequality), the approximation ratio is
222.
Example:

 Graph: A→B:10,B→C:15,C→A:20A \to B: 10, B \to C: 15, C \to A:


20A→B:10,B→C:15,C→A:20.
 MST: A−BA-BA−B, B−CB-CB−C.
 Approximate Tour: A→B→C→AA \to B \to C \to AA→B→C→A, cost = 45.
 Optimal Tour: A→B→C→AA \to B \to C \to AA→B→C→A, cost = 45 (optimal and
approximate are the same).

Conclusion

Approximation algorithms provide a trade-off between computational efficiency and


solution quality. They are practical for NP-hard problems, but their limitations, such as
suboptimal results and variability with input, must be carefully considered.

You might also like