Neste trabalho, investigamos uma série de problemas de clustering NP-difíceis. Começamos estudando o problema dos k-centros, também conhecido como k-center, um problema clássico para o qual Gonzalez apresentou em 1985 um algoritmo de aproximação com a melhor garantia de desempenho possível sob a menos que P = NP. Exploramos, em seguida, resultados disponíveis na literatura para diversas generalizações dos k-centros. Para a maioria desses problemas, ainda há espaço para melhorar os resultados conhecidos, seja na garantia de desempenho dos algoritmos ou em melhores resultados de impossibilidade de aproximação (resultados de inaproximabilidade). O trabalho inclui resultados originais obtidos para variantes do problema que combinam as restrições de capacidades dos centros e tolerância a falhas, Tais resultados incluem algoritmos com garantias de desempenho melhores que as dos algoritmos anteriormente descritos na literatura.

In this work, we investigate a series of NP-hard clustering problems. We begin looking at the k-center problem, a classic problem for which Gonzalez described in 1985 an approximation algorithm with the best possible approximation ratio unless P = NP. We then move on to describe other variants on the k-center problem. For most of these problems, there is still room for improving the known results, by reducing the approximation ratio of the best known algorithms or by obtaining stronger inapproximability results. This work also includes original results obtained for variants of the k-center problem with restricted capacities and fault tolerance. Such results include algorithms with approximation ratios lower than those previously known.