O problema da bissecção mínima

Resumo:

O problema da bissecção mínima de um grafo consiste em determinar um conjunto S com metade dos vértices do grafo que minimize o tamanho do corte \nabla(S). Trata-se de um problema NP-difícil bem conhecido.

Feige e Krauthgamer obtiveram (FOCS'2000) uma O(log² n)- aproximação para o problema da bissecção mínima. Essa aproximação depende do algoritmo de Sparsest Cut de Leighton e Rao (Journal of the ACM, 1999), que determina um corte de densidade aproximadamente mínima. (A densidade de um corte \nabla(S) é o quociente de |\nabla(S)| por |S||\bar{S}|.)

Nesta palestra, pretendo dar uma breve descrição dos dois algoritmos.