Disciplina Discipline MAC5727
Algoritmos de Aproximação

Approximation Algorithms

Área de Concentração: 45134

Concentration area: 45134

Criação: 22/06/2023

Creation: 22/06/2023

Ativação: 22/06/2023

Activation: 22/06/2023

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
4 2 4 12 semanas 12 weeks 120 horas 120 hours

Docentes Responsáveis:

Professors:

Yoshiko Wakabayashi

Cristina Gomes Fernandes

Objetivos:

Familiarizar os alunos com técnicas de projeto e análise de algoritmos de aproximação e com os resultados de inaproximabilidade. Estudar algoritmos de aproximação para vários problemas, dentre os quais destacamos problemas de escalonamento, bin packing, corte máximo, max SAT, projeto de redes e otimização em grafos.

Objectives:

Introduce the students to techniques used in the design of approximation algorithms, and techniques to prove inapproximability of certain problems. Study approximation algorithms for many problems, including those on scheduling, bin packing, max cut, max SAT, and many other optimization problems on graphs.

Justificativa:

Algoritmos de aproximação são uma alternativa muito usada no tratamento de problemas de otimização combinatória difíceis. Há uma variedade extensa destes algoritmos na literatura, e também de resultados de inaproximabilidade para tais problemas. Ter conhecimento nesta área é valioso para qualquer pesquisador que trabalhe com otimização ou projeto de algoritmos 1- Recapitulação de resultados básicos sobre grafos, complexidade computacional e probabilidade. 2- Métodos de projeto de algoritmos de aproximação: métricos, de arredondamento, probabilísticos, baseados em programação linear e semidefinida, primais-duais. 3- Algoritmos de aproximação para problemas de escalonamento, bin packing, projeto de redes e otimização em grafos. 4- Complexidade computacional: classes de complexidade Max SNP e APX, reduções, alguns resultados inaproximabilidade.

Rationale:

The use of approximation algorithms is an alternative to tackle hard combinatorial optimization problems. Many approximation algorithms as well as results on inapproximability of many problems have been presented in the literature. To be acquainted with the techniques and results in this area is valuable to any researcher who works in optimization and design of algorithms.

Conteúdo:

1- Recapitulação de resultados básicos sobre grafos, complexidade computacional e probabilidade. 2- Métodos de projeto de algoritmos de aproximação: arredondamento, probabilísticos, baseados em programação linear e semidefinida, primais-duais. 3- Algoritmos de aproximação para problemas de escalonamento, bin packing, projeto de redes e otimização em grafos. 4- Complexidade computacional: classes de complexidade Max SNP e APX, reduções, alguns resultados inaproximabilidade

Content:

1. Review of basic results in graphs, computational complexity, and probability. 2. Methods of design of approximation algorithms: metric, probabilistic, linear and semidefinite programming, primal-dual. 3. Approximation algorithms for scheduling, bib packing, network design, and optimization in graphs. 4. Computational complexity: Max SNP and APX classes, reductions, and inapproximability results.

Forma de Avaliação:

A avaliação será realizada através de seminários, projetos e provas. A nota final será calculada pela média obtida pelo aluno nos instrumentos de avaliação. Nas duas primeiras semanas de aula o docente fixará as datas e o número de provas, projetos e seminários, assim como o critério de atribuição do conceito final.

Type of Assessment:

The evaluation will be carried out through seminars, projects and tests. The final grade will be calculated by mean obtained by the student in the assessment instrument. In the first two weeks of class, the teacher will set the dates and number of tests, projects and seminars, as well as the criteria for attributing the final letter grade.

Bibliografia:

1. D.P. Williamson and D.B. Shmoys, The Desing of Approximation Algorithms, Cambridge University Press, 2011. 2. V. Vazirani, Approximation Algoritms, Springer, 2001. 3. M.H. de Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. de Pina Jr., J.A.R. Soares, Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, Publicações Matemáticas do IMPA, 2001. 4. D. Hochbaum (ed.), Approximation Algoritms for NP-hard Problems, PWS Publishing Caompany, 1997

Bibliography:

1. D.P. Williamson and D.B. Shmoys, The Desing of Approximation Algorithms, Cambridge University Press, 2011. 2. V. Vazirani, Approximation Algoritms, Springer, 2001. 3. M.H. de Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. de Pina Jr., J.A.R. Soares, Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, Publicações Matemáticas do IMPA, 2001. 4. D. Hochbaum (ed.), Approximation Algoritms for NP-hard Problems, PWS Publishing Caompany, 1997

Tipo de oferecimento da disciplina:

Presencial

Class type:

Presencial