• 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
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2019.tde-09102019-020507
Document
Author
Full name
Samuel Plaça de Paula
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2016
Supervisor
Committee
Fernandes, Cristina Gomes (President)
Pedrosa, Lehilton Lelis Chaves
Schouery, Rafael Crivellari Saliba
Title in Portuguese
Problema dos k-centros e variantes
Keywords in Portuguese
Algoritmos de aproximação
Clustering
Otimização combinatória
Abstract in Portuguese
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.
Title in English
The k-center problem and variants
Keywords in English
Approximation algorithms
Clustering
Combinatorial optimization
K-center
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
dissert_corrigida.pdf (941.04 Kbytes)
Publishing Date
2019-11-04
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2024. All rights reserved.