Ana səhifə

Universidade Federal de Pernambuco Graduação em Engenharia da Computação


Yüklə 47.25 Kb.
tarix12.06.2016
ölçüsü47.25 Kb.


Universidade Federal de Pernambuco
Graduação em Engenharia da Computação

Centro de Informática


2010.1




Otimização em Grafos:

árvores geradoras com restrições

Proposta de Trabalho de Graduação


Aluno Artur Ribeiro de Aquino {ara@cin.ufpe.br}

Orientador Liliane Rose Benning Salgado {liliane@cin.ufpe.br}

29 de Março de 2010



Sumário

1. Contexto 3

2. Objetivo 4

3. Cronograma 5

Referências 6

Assinaturas 8



1.Contexto


Otimização Combinatória é a área da matemática que estuda métodos para encontrar pontos ótimos (máximo ou mínimo) de uma função definida sob um certo domínio. Nos problemas desta área o domínio é finito, e os pontos podem ser enumerados. Entretanto, o número de pontos do domínio pode ser muito grande, inviabilizando uma abordagem que enumerasse todas as possibilidades.

Diversos problemas práticos podem ser modelados como problemas de Otimização Combinatória. Tais aplicações práticas motivam o estudo de abordagens exatas aproximadas para sua resolução, objeto principal de estudo neste projeto. A área de grafos tem sido tradicionalmente uma fonte de problemas interessantes de otimização combinatória, particularmente abordaremos os problemas de árvores geradoras com restrições.

O problema da árvore geradora de custo mínimo (MST-Minimal Spanning Tree) pode ser resolvido eficientemente utilizando algoritmos bem conhecidos na literatura, como o de Kruskal, Prim ou Boruvka. Porém, quando restrições adicionais (na sua altura, diâmetro, grau dos vértices, entre outros) são exigidas nestas árvores, o problema pode dar origem a variantes NP-difíceis.

O problema da árvore geradora com graus limitados é uma variante do MST em que, para cada vértice do grafo, é dada uma delimitação para o grau deste vértice na árvore geradora procurada. O problema foi estudado por Fürer e Raghavachari [1,2] e por Könemann e Ravi [3,4] e são conhecidas boas aproximações para diferentes variantes dele. Também, existem resultados de inaproximabilidade.

Outro problema de comum interesse na área é o da árvore geradora de diâmetro limitado. Este encontra importantes aplicações na indústria. Sabe-se que é NP-difícil. Inclusive, se limitarmos o diâmetro a 4, o problema fica tão difícil de aproximar quanto o Problema da Cobertura de Conjuntos (para o qual sabemos que não pode existir uma aproximação de razão (log n), onde n é o número de elementos no conjunto, a menos que P = NP). Bar-Ilan, Korsarz e Peleg mostram em [5] uma aproximação de razão logarítmica para os casos em que o diâmetro é́ limitado a 4 e a 5. Existe uma estreita relação entre este problema e o Problema da Localização de Facilidades, para o qual são conhecidas aproximações O(log n) [6,7].

Uma variante deste consiste em, dado um grafo conexo, encontrar uma árvore geradora de diâmetro mínimo. Hassin e Tamir [8] mostraram que esse problema pode ser resolvido em tempo polinomial mesmo quando cada aresta tem um comprimento dado e o diâmetro leva em conta esses comprimentos. A variante em que se busca uma árvore geradora de diâmetro mínimo (com comprimento nas arestas) e grau máximo limitado também é de interesse e se mostra bem mais difícil. Könemann, Levin e Sinha [9] apresentaram uma O(logB n) -aproximação para essa variante, onde B denota a limitação no grau máximo da árvore.


2.Objetivo


A proposta para este trabalho de graduação é estudar, na área de otimização combinatória, árvores geredoras com restrições e os algoritmos já existentes na literatura para a solução desse problema. Seguindo esse estudo deve-se fazer uma pesquisa na tentativa de elaborar um algortimo para algum dos vários tipos de restrições aplicáveis às árvores geradoras. Para decidir implementar o algortimo este teria que indicar ser uma solução interessante para o problema, ou seja, ele provavelmente apresentaria melhoras em algum aspecto sobre as soluções estudadas.

Após a implementação o algoritmo desenvolvido deve ser avaliado. Para isso, deverá ser determinada uma métrica de comparação para confrontar o algoritmo implementado com os estudados anteriormente. Desse modo será possível saber de fato a qualidade e até prever a utilidade do algoritmo implementado. No caso de não se chegar numa solução que possa ser considerada para implementação a comparação entre os algortimos já existentes e a identificação dos pontos de possíveis melhoras serão apresentadas.


3.Cronograma




Atividade

Abril

Maio

Junho

Levantamento bibliográfico





































Pesquisa e implementação





































Avaliação





































Relatório e apresentação






































Referências


­­­­­­­­­­­­­

[1] M. Fürer and B. Raghavachari. Approximating the minimum degree spanning tree to within

one from the optimal degree. In Proceedings of the Third ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 317–324, 1992.
[2] M. Fürer and B. Raghavachari. An NC approximation algorithm for the minimum degree

spanning tree problem. In Proceedings of the 28th Annual Allerton Conference on Communication, Control and Computing, pages 274–281, 1990.


[3] J. Könemann and R. Ravi. A matter of degree: improved approximation algorithms for

degree bounded minimum spanning trees. In Proceedings of the ACM Symposium of Theory

of Computing (STOC), pages 537–546, 2000.
[4] J. Könemann and R. Ravi. Primal-dual meets local search: approximating MSTs with no-

nuniform degree bounds. SIAM Journal on Computing, 34:763–773, 2005.


[5] J. Bar-Ilan, G. Kortsarz, and D. Peleg. Generalized submodular cover problems and appli-

cations. Theoretical Computer Science, 250:179–200, 2001.


[6] D.S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems.SIAM Journal on Computing, 11(3):555–556, 1982.
[7] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V.V. Vazirani. Greedy facility location

algorithms analyzed using dual fitting with factor-revealing. Journal of the ACM, 50(6):795–

824, 2003.
[8] R. Hassin and A. Tamir. On the minimum diameter spanning tree problem. Information

Processing Letters, 53(2):109–111, 1995.


[9] J. Könemann, A. Levin, and A. Sinha. Approximating the degree-bounded minimum diameter spanning tree problem. Algorithmica, 2004.


Assinaturas


Liliane Rose Benning Salgado

Orientador

Artur Ribeiro de Aquino



Aluno



Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©kagiz.org 2016
rəhbərliyinə müraciət