La Red Universitaria

Algoritmos de aproximación Parte I

Descripción

Algoritmos de aproximación, Parte I

¿Cuán eficientemente puede empaquetar objetos en un número mínimo de cajas? ¿Qué tan bien puede agrupar nodos para separar de manera económica una red en componentes alrededor de unos pocos centros? Estos son ejemplos de problemas de optimización combinatoria NP-hard. Es muy probable que sea imposible resolver tales problemas de manera eficiente, por lo que nuestro objetivo es dar una solución aproximada que pueda calcularse en tiempo polinómico y que al mismo tiempo tenga garantías demostrables sobre su costo en relación con el óptimo.

Este curso asume el conocimiento de un curso estándar de Algoritmos de pregrado, y enfatiza particularmente los algoritmos que pueden diseñarse usando programación lineal, una técnica favorita y sorprendentemente exitosa en esta área. Al tomar 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 redondeos aleatorios 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 primero de un curso de dos partes sobre Algoritmos de Aproximación.

Precio: ¡Inscríbase gratis!

Idioma: Inglés

Subtítulos: Inglés

Algoritmos de aproximación Parte I - École normale supérieure