Approximation algorithms

Polynomial-time approximate solutions.

Approximation algorithms

NP-complete problems require exponential time for exact solutions. An approximation algorithm produces a quality but not exact solution in acceptable time.

Approximation ratio measures how close the solution is to optimum. For example, a 2-approximation algorithm gives at most twice worse results.

Finding the maximum

Finding the largest element of an array is a simple starting point for approximation algorithms. Linear scan gives exact solution in O(n).

This example shows the 'good solution' concept underlying approximation algorithms. We will examine approximate and random methods in later steps.

Exercise find_max function

Write find_max(arr). Return the largest element of the array. Print 9 with print(find_max([3, 5, 7, 1, 9])).

Show example solution

def find_max(arr):
    # Find the largest element
    best = arr[0]
    for i in range(1, len(arr)):
        if arr[i] > best:
            best = arr[i]
    return best
print(find_max([3, 5, 7, 1, 9]))

Test yourself

What does an approximation algorithm provide?
- Exact solution
- Fast and close solution
- No solution
- Random solution
Show answer

Fast and close solution — Approximation gives a fast and close solution.
Finding max
```
best = arr[____]
```
Show answer
```
best = arr[0]
```
Approximation algorithms: match the terms

approximation

Approximate
ratio

Ratio
NP-complete

Hard
fast

O(n)

Next lesson: Randomized algorithms

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies