Algoritmos exatos e de aproximação para agrupamento

Neste artigo, apresentamos um algoritmo que funciona em tempo O(n k^{1-1/d}) para resolver o problema do k-centro em R^d, sob as métricas L1 e L2. O algoritmo se estende a outras métricas e pode ser usado para resolver o problema discreto do k-centro também. Também descrevemos um algoritmo simples de aproximação (1 + ε) para o problema do k-centro, com tempo de execução O(n log k) + (k = ) O(k^{1-1/d}). Finalmente, apresentamos um algoritmo que funciona em tempo O(n k^{1-1/d}) para resolver o problema do k-centro com capacitação L, desde que L = (n/k)^{1-1/d} ou L = O(1). Concluímos com um algoritmo de aproximação simples para o problema do k-centro com capacitação L.