Exportar registro bibliográfico

Aproximação de métricas finitas por métricas arbóreas e aplicações (2011)

  • Authors:
  • USP affiliated authors: LIMA, MURILO SANTOS DE - IME
  • Unidades: IME
  • Sigla do Departamento: MAC
  • Subjects: OTIMIZAÇÃO COMBINATÓRIA
  • Agências de fomento:
  • Language: Português
  • Abstract: 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
  • Online source access
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      LIMA, Murilo Santos de; FERNANDES, Cristina Gomes. Aproximação de métricas finitas por métricas arbóreas e aplicações. 2011.Universidade de São Paulo, São Paulo, 2011. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/ >.
    • APA

      Lima, M. S. de, & Fernandes, C. G. (2011). Aproximação de métricas finitas por métricas arbóreas e aplicações. 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, Fernandes CG. Aproximação de métricas finitas por métricas arbóreas e aplicações [Internet]. 2011 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/
    • Vancouver

      Lima MS de, Fernandes CG. Aproximação de métricas finitas por métricas arbóreas e aplicações [Internet]. 2011 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13032012-201516/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020