Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example because the problems are NP-hard. The goal of this 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.
Offert par
Approximation Algorithms
EIT DigitalÀ propos de ce cours
Certificat partageable
Obtenez un Certificat lorsque vous terminez
100 % en ligne
Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles
Réinitialisez les dates limites selon votre disponibilité.
Niveau intermédiaire
Approx. 15 heures pour terminer
Anglais
Sous-titres : Anglais
Certificat partageable
Obtenez un Certificat lorsque vous terminez
100 % en ligne
Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles
Réinitialisez les dates limites selon votre disponibilité.
Niveau intermédiaire
Approx. 15 heures pour terminer
Anglais
Sous-titres : Anglais
Offert par
EIT Digital
EIT Digital is a European education and innovation organisation with a mission to foster digital technology innovation and entrepreneurial talent for economic growth and quality of life. By linking education, research and business, EIT Digital empowers digital top talents for the future.
Programme du cours : ce que vous apprendrez dans ce cours
1 heure pour terminer
Introduction to Approximation algorithms
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.
1 heure pour terminer
1 vidéo (Total 13 min), 1 lecture, 1 quiz
5 heures pour terminer
The Load Balancing problem
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).
5 heures pour terminer
3 vidéos (Total 45 min), 1 lecture, 2 quiz
3 heures pour terminer
LP Relaxation
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.
3 heures pour terminer
6 vidéos (Total 69 min), 2 lectures, 1 quiz
6 heures pour terminer
Polynomial-time approximation schemes
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.
6 heures pour terminer
6 vidéos (Total 62 min), 2 lectures, 2 quiz
Avis
Meilleurs avis pour APPROXIMATION ALGORITHMS
par SM10 oct. 2020
Please try to include some more numeric example like load balancing problem in the vertex cover and rest topics
Foire Aux Questions
Quand aurai-je accès aux vidéos de cours et aux devoirs ?
À quoi ai-je droit si j'achète le Certificat ?
Is financial aid available?
Puis-je obtenir des crédits universitaires si je réussis le Cours ?
D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.
