Algoritmos de Aproximação para Problemas de Localização com Diferentes Funções de Distância

Resumo

Neste projeto, estamos interessados em investigar o Problema de Localização de Facilidades (FLP), k-Means e problemas correlatos com outras restrições de conectividade. Nosso interesse será focado em estratégias recentes desenvolvidas para estes problemas, principalmente aquelas que levam a bons fatores de aproximação e resultados práticos. Algoritmos de aproximação é uma das áreas que têm recebido grande atenção dos pesquisadores de otimização e teoria da computação nos últimos anos. Esses algoritmos são utilizados principalmente em problemas NP-difícies, para os quais um algoritmo exato seria inviável. Existem diferentes técnicas para o desenvolvimento de algoritmos de aproximação, que têm sido utilizadas para obter aproximações cada vez melhores para os problemas de localização e vários outros. Diversos algoritmos de aproximação para problemas, como o FLP ou o TSP, utilizam fortemente o fato de que as funções de distância subjacentes sejam métricas para obter resultados de aproximação. Para algumas aplicações, no entanto, as funções de distância não obedecem à desigualdade triangular, como é o caso do k-Means, que utiliza a distância euclidiana ao quadrado. Um dos principais objetivos deste projeto é investigar estes problemas usando outras funções de distância e investigaremos as consequências para a aproximação.