Approximation Algorithm - Part 1

 Introduction

To solve any problem we need to design an algorithm. We can design many different types of algorithms but we need an efficient one. Problems for which an efficient algorithm exists is called P-type problem. But there are some problems which we do not find any efficient algorithm. (NP-hard)

Polynomial Time

 

§Linear Search ----------O( n)

 

§Binary Search---------- O(log n)

 

§Insertion sort------------- O(n2)

 

§Merge sort----------- O(nlogn)

 

§Matrix Multiplication ------- O(n3)

 

Exponential Time

 

§0/1 knapsack problem

 

§Traveling salesman

 

§Sum of subsets

 

§Graph coloring

 

§Hamilton cycle

 O( Kn )

 

Optimization Problem

§In mathematics and computer science, an optimization problem is a problem of finding the best solution from all feasible solutions.

§The objective may be either min. or max. depending on the problem considered.

§A large number of optimization problems which are required to be solved in practice are NP-hard.

 

§For such problems, it is not possible to design algorithms that can find an exactly the optimal solution to all instances of the problem in polynomial time in the size of the input, unless P = NP .

Strategies to cope with NP-complete problems

1. If inputs are small, an algorithm with exponential running time may be satisfactory.

 

2. Isolate important special cases that can be solved in polynomial-time.

 

3. Develop algorithms that find near-optimal solutions in polynomial-time.

 Performance Bounds

• Let C be the cost of the solution produced by our approximation algorithm. 

• C* be the optimal solution.

• We will assume that costs are strictly positive values.

 

§Maximization problem

 

v0 < C <= C*

 

vC* / C factor by which the cost of the optimal the solution is larger than the cost of the approximate solution

§Minimization problem

 

v0 < C* <= C

 

vC / C* factor by which the cost of the an approximate solution is larger than the cost of the optimal solution

 

 

§Observe that p(n) is always greater than or equal to 1, and it is equal to 1 if and only if an approximate solution is the true optimum solution.

 Approximation Algorithm

§Algorithm should run in polynomial time.

§Will not give exact solutions but instead will give near-optimal solutions.

§ The algorithm has an approximation ratio p(n). if: