Approximation Algorithms

Approximation Algorithms

Instructor: Mark de Berg

Access provided by CelcomDigi Berhad

6,876 already enrolled

4 modules

Gain insight into a topic and learn the fundamentals.

33 reviews

Intermediate level

Some related experience required

2 weeks to complete

at 10 hours a week

Flexible schedule

Learn at your own pace

4 modules

Gain insight into a topic and learn the fundamentals.

33 reviews

Intermediate level

Some related experience required

2 weeks to complete

at 10 hours a week

Flexible schedule

Learn at your own pace

Skills you'll gain

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

4 assignments

Taught in English

See how employees at top companies are mastering in-demand skills

Learn more about Coursera for Business

logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

There are 4 modules in this course

Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example, because the problems are NP-hard. The goal of the Approximation Algorithms course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. These techniques apply when we don't require the optimal solution to certain problems, but an approximation that is close to the optimal solution. We will see how to efficiently find such approximations.

Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, stacks, queues, heaps - (Balanced) binary search trees - Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort - Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths) The material for this course is based on the course notes that can be found under the resources tab.

In the module the motivation for studying approximation algorithms will be given. We will discuss what optimization problems are, and what the difference between heuristics and approximation algorithms is. Finally, we will introduce the concept of approximation ratio, which plays a central role in the analysis of the quality of approximation algorithms.

What's included

1 video1 reading1 assignment

In this module we will study various approximation algorithms for the load balancing problem. This problems asks to distribute a given set of jobs, each with a certain processing time, over a number of machine. The goal is to do this such that all jobs are finished as soon as possible. We will analyze the quality of the computed solutions computed using the concept of rho-approximation, which we saw in the previous lecture. In this analysis we will see that lower bounds on the optimal solution play a crucial role in the analysis (or, for maximization problems: upper bounds).

What's included

3 videos1 reading1 assignment1 programming assignment

In this module we will introduce the technique of LP relaxation to design approximation algorithms, and explain how to analyze the approximation ratio of an algorithm based in LP relaxation. We will do this using the (weighted) Vertex Cover problem as an example. Before we explain the technique of LP relaxation, however, we first give a simple 2-approximation algorithm for the unweighted Vertex Cover problem.

What's included

6 videos2 readings1 assignment

6 videos Total 69 minutes

The vertex-cover problem 10 minutes
An approximation algorithm for vertex-cover 11 minutes
A brief introduction to linear programming 13 minutes
Weighted vertex-cover 15 minutes
LP relaxation for weighted vertex-cover 7 minutes
LP relaxation: Analyzing approximation ratio 13 minutes

2 readings Total 65 minutes

Course notes 3.1 20 minutes
Course notes 3.2 45 minutes

1 assignment Total 30 minutes

LP Relaxation 30 minutes

In this module we will introduce the concept of Polynomial-Time Approximation Scheme (PTAS), which are algorithms that can get arbitrarily close to an optimal solution. We describe a general technique to design PTASs, and apply it to the famous Knapsack problem. Finally we will see how to analyze PTASs that are designed with the general technique.