O Problema do K-Corte Mínimo

Resumo:

Seja (G,c) um par que consiste de um grafo G = (V, A) e uma função custo c que associa a cada aresta de G um racional não-negativo. Dado um par (G,c) e uma seqüência K= (k₁, k₂,..., k_p) de p inteiros positivos tal que $\sum_{i=1}^p k_i ‹= |V|$, o Problema do K-Corte Mínimo consiste em encontrar p blocos, isto é, subconjuntos disjuntos V_i de V, com |V_i|=k_i (i=1,...,p), que minimiza a soma dos custos das arestas cujos extremos pertencem a blocos distintos.

Discutiremos este problema e outros correlatos, abordando aspectos computacionais e resultados conhecidos. Em particular, mostraremos um algoritmo de 3-aproximação para qualquer p fixo, p›=2.