MO418/MC748 - Approximation Algorithms

MO418/MC748 - Algoritmos de Aproximação

MO418/MC748 - Algoritmos de Aproximación

"...all exact science is dominated by the idea of approximation." "...toda ciência exata é dominada pela ideia de aproximação." "...toda ciencia exacta es dominada por la idea de aproximación."
Bertrand Russell

This graduate course in Computer Science focuses on strategies for designing approximation algorithms. It also explores approximation boundaries and approximation complexity classes (PO, FPTAS, PTAS, APX, NPO), including hardness and completeness proofs. By the end of the semester, students are expected to analyze the approximability of combinatorial optimization problems and design approximation algorithms, proving the correctness of their approximation factors.

Esta disciplina de pós-graduação em Ciência da Computação aborda estratégias para o projeto de algoritmos de aproximação. Além disso, explora limites de aproximação e classes de complexidade de aproximação (PO, FPTAS, PTAS, APX, NPO), incluindo provas de dificuldade e completude. Ao final do semestre, espera-se que os alunos sejam capazes de analisar a aproximabilidade de problemas de otimização combinatória e projetar algoritmos de aproximação, demonstrando a correção de seus fatores de aproximação.

Esta asignatura de posgrado en Ciencias de la Computación se centra en estrategias para el diseño de algoritmos de aproximación. Además, explora los límites de aproximación y clases de complejidad de aproximación (PO, FPTAS, PTAS, APX, NPO), incluyendo pruebas de dificultad y completitud. Al final del semestre, se espera que los estudiantes sean capaces de analizar la aproximabilidad de problemas de optimización combinatoria y diseñar algoritmos de aproximación, demostrando la corrección de sus factores de aproximación.


Offering: 1st semester of 2025Oferecimento: 1ro semestre de 2025Oferta: 1er semestre de 2025
Schedule: Tuesday and Thursday, from 2:00PM. to 4:00PM.Horário: Terça-feira e Quinta-feira, das 14:00 às 16:00Horario: Martes y Jueves, de las 2:00PM. a las 4:00PM.
Location: Local: Localización: CC52
PDD: Download here Baixe aqui Baje aquí
Timeline: Cronograma: Cronograma: Download here Baixe aqui Baje aquí

Bibliography

Bibliografia

Bibliografía

Main references

Referências principais

Referencias principales


David P. Williamson, David B. Shmoys. "The design of Approximation Algorithms". Cambridge University Press. (2011).
Vijay V. Vazirani. "Approximation Algorithms". Springer Berlin, Heidelberg. (2003).

Complementary references

Referências complementares

Referencias complementares


Edited by Dorit S. Hochbaum. "Approximation Algorithms for NP-Hard Problems". PWS Publishing Company, Boston, MA. (1996).
Marcelo H. Carvalho et al. "Uma Introdução Sucinta a Algoritmos de Aproximação". (2001).

T. Cormen, C. Leiserson, R. Rivest, C. Stein. "Introduction to Algorithms". MIT Press (MA); 3rd ed. (2009).

Lectures

Aulas

Clases

The slides will be added after each lecture. These can be used as a guide to review the lessons. To study and practice, you should read the main bibliography and solve the suggested exercises.

Os slides serão disponilizados após cada aula. Estes podem ser usados como guia para revisar as aulas. Para estudar e praticar, devem ler a bibliografia principal e resolver os exercícios sugeridos.

Los slides serán disponibilizados después de cada clase. Estos pueden ser utilizados como guía para revisar las lecciones. Para estudiar y practicar, deben leer la bibliografía principal y resolver los ejercicios sugeridos

Topics Tópicos Asuntos
slides (Portuguese only) slides (somente em Português) slides (solo en Portugués)
Lecture 01 - Introduction Aula 01 - Introdução Aula 01 - Introducción
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 02 - Introduction Aula 02 - Introdução Aula 02 - Introducción
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 03 - Introduction (exercises) Aula 03 - Introdução (exercícios) Aula 03 - Introducción (ejercicios)
Download here Baixe aqui Baje aquí
Lecture 04 - Approximation and bounds Aula 04 - Aproximação e limitantes Aula 04 - Aproximación y límites
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 05 - Linear programming bounds Aula 05 - Limitantes via programação linear Aula 05 - Límites por programación lineal
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 06 - Greedy approximation algorithms Aula 06 - Algoritmos de aproximação gulosos Aula 06 - Algoritmos de aproximación golosos
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 07 - Approximating the Traveling Salesman problem Aula 07 - Aproximando o Caixeiro Viajante Aula 07 - Aproximando el Agente Viajero
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 08 - Maximizing submodular functions Aula 08 - Maximizando funções submodulares Aula 08 - Maximizando funciones submodulares
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 09 - Local search Aula 09 - Busca local Aula 09 - Búsqueda local
Download here Baixe aqui Baje aquí
Handout Handout Handout
Lecture 10 - Local search for the minimum max-degree spanning tree Aula 10 - Busca local para árvore geradora de graus mínimos Aula 10 - Búsqueda local para el árbol generador de grados mínimos
Download here Baixe aqui Baje aquí
Handout Handout Handout

Acknowledgment: In the preparation of the teaching materials, lecture notes kindly provided by Prof. Lehilton Lelis Chaves Pedrosa were used. The available materials were prepared by me and may contain errors, which I kindly ask to be reported.

Agradecimentos: Na preparação do material didático, foram utilizadas notas de aula gentilmente cedidas pelo Prof. Lehilton Lelis Chaves Pedrosa. O material disponibilizado foi elaborado por mim e pode conter erros, os quais peço que sejam reportados.

Agradecimientos: En la preparación del material didáctico, se utilizaron apuntes de clase gentilmente proporcionados por el Prof. Lehilton Lelis Chaves Pedrosa. El material disponible fue elaborado por mí y puede contener errores, los cuales agradecería que me fueran reportados.

Exercises lists

Listas de exercícios

Listas de ejercicios

The files will be added during the course.

Os arquivos serão adicionados durante o curso.

Los archivos serán adicionados durante el curso.

files (Portuguese only) arquivos (somente em Português) archivos (solo en Portugués)
Diagnostic assessment Avaliação diagnóstica Evaluación diagnóstica
Download here Baixe aqui Baje aquí
Exercise List 01 Lista de exercícios 01 Lista de ejercicios 01
Download here Baixe aqui Baje aquí


Grades

Notas

Notas

Evaluation method

Método de avaliação

Método de evaluación


Four exercises lists: L1, L2, L3, and L4. One report: R, and one seminar: S. The average grade will be given by M=0.5(L1+L2+L3+L4)/4+0.2R+0.3S. The final grades will be: A if M in [8.5,10], B if M in [7,8.5), C if M in [5,7), and D if M in [0,5).

Quatro listas de exercícios: L1, L2, L3 e L4. Um relatório: R, e um seminário: S. A média será dada por M=0.5(L1+L2+L3+L4)/4+0.2R+0.3S. O conceito final será: A se M está em [8.5,10], B se M está em [7,8.5), C se M está em [5,7) e D se M está em [0,5).

Cuatro listas de ejercicios: L1, L2, L3 y L4. Un relatorio: R, y un seminario: S. La media será dada por M=0.5(L1+L2+L3+L4)/4+0.2R+0.3S. La nota final será: A si M está en [8.5,10], B si M está en [7,8.5), C si M está en [5,7), y D si M está en [0,5).

Any detection of fraud will result in a grade of D.

Qualquer detecção de fraude implicará em finalizar com conceito D.

Cualquier detección de fraude implicará terminar con nota D.

Files

Arquivos

Archivos


Attendance and grade files will be uploaded here.

Arquivos com as notas e a frequência serão disponibilizados aqui.

Archivos con las notas y la asiduez serán disponibilizados aquí.