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: 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
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.
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í.