• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
10.11606/D.45.2011.tde-13032012-201516
Documento
Autor
Nombre completo
Murilo Santos de Lima
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2012
Director
Tribunal
Fernandes, Cristina Gomes (Presidente)
Feofiloff, Paulo
Lee, Orlando
Título en portugués
Aproximação de métricas finitas por métricas arbóreas e aplicações
Palabras clave en portugués
aproximação de métricas
emparelhamento mínimo bipartido online
métricas arbóreas
Resumen en portugués
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.
Título en inglés
Approximation of finite metrics by tree metrics and applications
Palabras clave en inglés
metric approximation
online minimum bipartite matching
tree metrics
Resumen en inglés
Many optimization problems on graphs, especially metric problems, are easier to solve on trees. Therefore, a strategy for obtaining a good algorithm for certain problems is to obtain a tree that approximates the graph, and use a solution of the problem on the tree as an approximate solution for the problem on the original graph. We study the work of Fakcharoenphol, Rao e Talwar, who showed how to approximate an arbitrary finite metric on n points by a tree metric with expected distortion O(lg n), which is asymptotically optimum. This strategy leads to algorithms with good approximation factors, and to competitive algorithms for various optimization problems, some of them online and distributed. Here, we present the application of that technique to the problem of finding a minimum online matching on a bipartite metric graph. This problem illustrates how metric approximation aids in solving a problem, and the care that must be taken when doing such an application.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2012-03-19
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.