MO418/MC748 - Approximation Algorithms
MO418/MC748 - Algoritmos de Aproximação
MO418/MC748 - Algoritmos de Aproximación
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: 2nd semester of 2026Oferecimento: 2do semestre de 2026Oferta: 2do semestre de 2026
Schedule: Monday and Wednesday, from 7:00PM. to 9:00PM.Horário: Segunda-feira e Quarta-feira, das 19:00 às 21:00Horario: Lunes y Miércoles, de las 7:00PM. a las 9:00PM.
Location: Local: Localización: CC52
Timeline: Cronograma: Cronograma: Download here Baixe aqui Baje aquí
Bibliography
Bibliografia
Bibliografía
Main references
Referências principais
Referencias principales
Complementary references
Referências complementares
Referencias complementares
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
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.