Essa edição do Workshop Paulista em Otimização, Combinatória e Algoritmos contou com pesquisadores das seguintes instituições:

• Instituto de Matemática Pura e Aplicada (IMPA)

• Universidade de São Paulo (USP)

• Universidade Estadual de Campinas (Unicamp)

• Universidade Federal do ABC (UFABC)

• Universidade Federal Fluminense (UFF)

• Universidad de Valparaíso (UV)

• Charles University (CUNI)

Algoritmos de aproximação - Profa. Cristina Gomes Fernandes

Many well-known optimization problems are hard to solve, meaning that the existence of a polynomial-time algorithm for solving them would imply that P = NP. Approximation algorithms are a possible way to reasonably deal with hard optimization problems. The goal of such algorithms is to efficiently produce feasible solutions that are close, in some sense, to an optimal solution for the problem. Such algorithms can be thought of as heuristics that have a performance guarantee in terms of the quality of the solution produced. We will present an introduction to the study of approximation algorithms, starting from simple examples, and gradually covering different techniques used in the area. In the process of presenting such techniques, we will address a variety of optimization problems such as scheduling, clustering, and satisfiability. The first half of the tutorial will be easily followed by anyone with a background on algorithms, and with basic notions of complexity theory. The second half will present techniques that involve linear programming and/or probabilistic strategies. 

Slides disponíveis.

Os gastos com hospedagem, café da manhã, almoço, jantar e coffee breaks dos participantes que não são alunos FAPESP ficam por conta da organização do evento (exceto bebidas).

Eventuais despesas extras (frigobar, etc.) não serão pagas pela organização do evento.

Gastos com transporte ficam a cargo dos participantes.

 Link para todas as fotos