Estrutura em Classes de Aproximação

Katia Guimarães (DI/UFPE)

Resumo: A noção de problemas aproximáveis e algoritmos de aproximação foi introduzida formalmente por Johnson, em 1974, que sugeriu a classificação de problemas de acordo com suas propriedades de aproximação. Embora as versões de decisão dos problemas de otimização NP-completos sejam redutíveis uma à outra em tempo polinomial, tais reduções quando transplantadas para a perspectiva de otimização, nem sempre preservam a função objetivo, e raramente preservam a qualidade das soluções obtidas. Torna-se necessário, portanto, usar reduções mais restritas, que além de mapear instâncias do problema A em instâncias de B, também garantam que boas soluções para B, gerem boas soluções para A. Nesta palestra discutiremos um conjunto de reduções e suas propriedades. Iniciaremos com a tradicional L-redução de Papadimitriou & Yannakakis, identificando alguns problemas estruturais; discutiremos a E-redução, que é mais robusta, mas também apresenta problemas, e por fim discutiremos a AP -redução, recentemente proposta por Crecenzi, Kann, Silvestri & Trevisan, e alguns dos resultados estruturais que o seu uso permitiu provar.