skip to main content
Idioma:

Problema dos k-centros e variantes

Paula, Samuel Plaça De

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2016-12-19

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Problema dos k-centros e variantes
  • Autor: Paula, Samuel Plaça De
  • Orientador: Fernandes, Cristina Gomes
  • Assuntos: Algoritmos De Aproximação; Clustering; Otimização Combinatória; Approximation Algorithms; Combinatorial Optimization; K-Center
  • Notas: Dissertação (Mestrado)
  • Descrição: Neste trabalho, investigamos uma série de problemas de clustering NP-difíceis. Começamos estudando o problema dos k-centros, também conhecido como k-center, um problema clássico para o qual Gonzalez apresentou em 1985 um algoritmo de aproximação com a melhor garantia de desempenho possível sob a menos que P = NP. Exploramos, em seguida, resultados disponíveis na literatura para diversas generalizações dos k-centros. Para a maioria desses problemas, ainda há espaço para melhorar os resultados conhecidos, seja na garantia de desempenho dos algoritmos ou em melhores resultados de impossibilidade de aproximação (resultados de inaproximabilidade). O trabalho inclui resultados originais obtidos para variantes do problema que combinam as restrições de capacidades dos centros e tolerância a falhas, Tais resultados incluem algoritmos com garantias de desempenho melhores que as dos algoritmos anteriormente descritos na literatura.
  • DOI: 10.11606/D.45.2019.tde-09102019-020507
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2016-12-19
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Resultado  1 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.