• 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
Documento
Autor
Nombre completo
Samuel Plaça de Paula
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2016
Director
Tribunal
Fernandes, Cristina Gomes (Presidente)
Pedrosa, Lehilton Lelis Chaves
Schouery, Rafael Crivellari Saliba
Título en portugués
Problema dos k-centros e variantes
Palabras clave en portugués
Algoritmos de aproximação
Clustering
Otimização combinatória
Resumen en portugués
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.
Título en inglés
The k-center problem and variants
Palabras clave en inglés
Approximation algorithms
Clustering
Combinatorial optimization
K-center
Resumen en inglés
In this work, we investigate a series of NP-hard clustering problems. We begin looking at the k-center problem, a classic problem for which Gonzalez described in 1985 an approximation algorithm with the best possible approximation ratio unless P = NP. We then move on to describe other variants on the k-center problem. For most of these problems, there is still room for improving the known results, by reducing the approximation ratio of the best known algorithms or by obtaining stronger inapproximability results. This work also includes original results obtained for variants of the k-center problem with restricted capacities and fault tolerance. Such results include algorithms with approximation ratios lower than those previously known.
 
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.
dissert_corrigida.pdf (941.04 Kbytes)
Fecha de Publicación
2019-11-04
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.