Paulo Feofiloff
IME-USP
Sexta-feira, 24 de outubro de 2003, 14:00
Sala 266, Bloco A, IME-USP
Resumo:
O problema da k-bipartição de um grafo consiste em determinar um conjunto S de vértices que minimize o corte \nabla(S) sob a restrição |S| = k. O caso k = n/2 é conhecido como problema da bisseção mínima (como de hábito, n é o número de vértices do grafo). Os problemas são NP-difíceis.
Esta palestra pretende discutir (de maneira elementar e superficial) algumas heurísticas e algoritmos de aproximação para o problema da bipartição equilibrada.
Eu deveria ter feito esta exposição introdutória antes da palestra "O problema da bisseção mínima" de 27 de junho passado, que tentou esboçar a O(log2 n)-aproximação de Feige e Krauthgamer para o problema da bisseção.
Referências:
U. Feige, R. Krauthgamer, "A polylogarithmic approximation of the minimum bisection", SIAM Journal on Computing, v.31, 2002.
U. Feige, R. Krauthgamer, K. Nissim, "On cutting a few vertices from a graph", Discrete Applied Mathematics, v.127, 2003.
G. Even, J. Naor, S. Rao, B. Schieber, "Fast Approximate graph partitioning algorithms", SIAM Journal on Computing, 28, 1999.