Algoritmos de aproximación Parte II

Descripción

Algoritmos de aproximación, parte 2

Esta es la continuación de los algoritmos de aproximación, Parte 1. Aquí aprenderá la dualidad de programación lineal aplicada al diseño de algunos algoritmos de aproximación, y la programación semidefinida aplicada a Maxcut.

Al tomar las dos partes de este curso, estará expuesto a una variedad de problemas en los fundamentos de la informática teórica y a poderosas técnicas de diseño y análisis. Al finalizar, podrá reconocer, cuando se enfrente a un nuevo problema de optimización combinatoria, si está cerca de uno de los pocos problemas básicos conocidos, y podrá diseñar relajaciones de programación lineal y utilizar redondeo aleatorio para intentar resolver su problema. propio problema El contenido del curso y, en particular, la tarea es de naturaleza teórica sin ninguna tarea de programación.

Este es el segundo curso de dos partes sobre algoritmos de aproximación.