Aproximação de métricas finitas por métricas arbóreas e aplicações (2011)
- Autores:
- Autor USP: LIMA, MURILO SANTOS DE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Idioma: Português
- Resumo: Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação.
- Imprenta:
- Data da defesa: 15.12.2011
-
ABNT
LIMA, Murilo Santos de. Aproximação de métricas finitas por métricas arbóreas e aplicações. 2011. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2011. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/. Acesso em: 19 abr. 2024. -
APA
Lima, M. S. de. (2011). Aproximação de métricas finitas por métricas arbóreas e aplicações (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/ -
NLM
Lima MS de. Aproximação de métricas finitas por métricas arbóreas e aplicações [Internet]. 2011 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/ -
Vancouver
Lima MS de. Aproximação de métricas finitas por métricas arbóreas e aplicações [Internet]. 2011 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
