UFC - Bacharelado em Ciência da Computação

Algoritmos Aproximativos (graduação CK132, pós CKP8099)

Semestre: 2020.2
Horário: Segundas e Quartas 14:00-16:00
Local: Aulas Remotas
Atendimento: Por meio do SIGAA da disciplina.

Apresentação:

Listas de Exercícios

Ementa:

Ementa Oficial (MDCC-UFC) (CC-UFC)

Um algoritmo aproximativo é um algoritmo que retorna um valor não necessariamente ótimo, mas um garantia de proximidade do ótimo. Por exemplo, um algoritmo de minimização (maximização) é 2-aproximativo se sua resposta é no pior caso duas vezes maior (menor) que o ótimo. O conteúdo deste curso é formado por diversos exemplos e técnicas de algoritmos aproximativos. A ementa do curso é a seguinte:

Introdução - Definições
Algoritmos Clássicos

Problema da Mochila (slides)
Caixeiro Viajante (TSP - Travelling Salesman Problem)
Caixeiro Viajante Métrico - TSPM (slides)
Cobertura por Conjuntos e Cobertura por Vértices (slides)
Bin Packing (slides)
Escalonamento (slides)
MAXSAT (slides)

Complexidade de Problemas de Otimização quanto à Aproximabilidade

Definições básicas
Classes de Aproximabilidade APX, PTAS e FPTAS (slides)
Relações entre as classes

Algoritmos de Programação Matemática

Cobertura por Conjuntos e Cobertura por Vértices (slides)
Hitting Set (Transversal) (slides)
MAXSAT (slides)
MAXCUT e MAX-2SAT (Programação Semidefinida) (slides)
Correlational Clustering (Programação Semidefinida) (slides)

Dificuldade de Aproximação

Reduções que preservam aproximação - Definições (slides)
Redução AP - Exemplos - Problemas APX-Completos e NPO-Completos (slides)
Teorema PCP (Probabilistically Checkable Proofs) (slides)

Avaliação:

1 Prova, 2 Listas de exercicios e 2 Apresentações

Livro-texto:

V.V.Vazirani, Approximation Algorithms, Springer, 2001, disponivel aqui

Bibliografia adicional:

Carvalho, Cerioli, Dahab, Feofiloff, Fernandes, Ferreira, Guimarães, Miyazawa, Pina Jr, Soares, Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, IMPA, 2001, disponivel aqui