Algoritmos de aproximação para partições conexas em grafos

Autor(es)

Liliane Rose Benning Salgado

• Tipo de documento: Tese de Doutorado
• Imprenta: São Paulo.
• Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Data de defesa: 2004-03-22
• Orientador: Yoshiko Wakabayashi

Resumo

O estudo das propriedades de aproximação de problemas de otimização NP-difíceis é um tópico de interesse tanto da área de otimização quanto da teoria de comploexidade computacional. O tema desta tese insere-se neste contexdto, dando ênfase ao estudo de problemas de partição de grafos em subgrafos conexos satisfazendo certas especificações. Concentramo-nos no desenvolvimento e análise de algoritmos de aproximação, e questões relativas ao grau de (in)aproximabilidade desses problemas. Um dos problemas investigados, chamado Max 2-Partição Conexa Balanceada ('PCB IND. 2'), é o seguinte: dado um grafo conexo G=(V, E) com uma função peso w : V -> 'Z IND. +' definida sobre seus vértices, encontrar uma 2-partição ('V IND. 1', 'V IND. 2') de V tal que G['V IND. 1'] e G['V IND. 2'] sejam conexos e o peso do mais `leve¦ deles seja o maior possível. Mais formalmente, queremos encontrar uma tal partição que maximiza a função min {w('V IND. 1'), w('V IND. 2')}, onde w(S) denota o peso de um conjunto S. Exibimos resultados sobre complexidade computacional e inaproximabilidade. Também apresentamos uma releitura de um algoritmo (4/3)-aproximado desenvolvido por Chlebíková [Ch196]. A análise parametrizada que fizemos permite descrever classes de grafos para as quais as soluções devolvidas se aproximam assintoticamente do ótimo. Mostramos que a razão de aproximação desse algoritmo é justa mesmo para grafos 3-conexos. Além disto, elaboramos um algoritmo para grafos 3-conexos usando contrações de arestas, que pode produzir soluções de qualidade melhor do que o algoritmo (4/3)-aproximado. Também apresentamos um esquema de aproximação polinomial para uma classe especial de grafos. Provamos ainda que as versões com e sem pesos do Max 2-Partição Conexa Balanceada possuem o mesmo limiar de aproximação. Estudamos também uma generalização natural do problema 'PCB IND 2', denominado Max q-Partição Conexa Balanceada Continua. Continuação: ('PCB IND. q'), para q > 2. Para o problema 'PCB IND. 3' restrito a grafos 3-conexos exibimos dois algoritmos, sendo um deles uma 2-aproximação. Para 'PCB IND. 4' restrito a grafos 4-conexos exibimos também uma 2-aproximação, porém apenas sob certas hipóteses sobre os pesos dos vértices. Investigamos um outro problema, chamado Max Árvore Balanceada, que mostramos ser AP-redutível ao 'PCB IND. 2'. Também apresentamos algoritmos de aproximação para um outro problema correlato, denominado Max (p/k)-Bipartição Fracionária Conexa. Exibimos um algoritmo para 1/2 menor ou igual a p/k < 1 cuja razão de aproximação é 3p/(3p-k). Discutimos brevemente outros problemas correlatos, mencionando alguns resultados encontrados na literatura. (AU)

• Processo FAPESP: 98/02407-9 - Aproximabilidade de problemas de otimização em grafos
• Beneficiário: Liliane Rose Benning Salgado
• Modalidade de apoio: Bolsas no Brasil - Doutorado