logo-mooc
search-iconsearch-icon
menu-whitemenu-blue
GRATIS
Inicio / Buscador / Ciencias de la Computacion /
IE Business School vía Coursera
GRATIS

Approximation Algorithms

  • money

    Cursos gratis (Auditar)

    question-mark
  • earth

    Inglés

  • folder

    Siempre Abierto

  • certificate

    Guía de Registro en Coursera

    arrow
VER CURSO arrow
Acerca de este curso

  • 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.
  • 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).
  • 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.
  • 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.