Problema dos k-centros e variantes (2016)
- Authors:
- Autor USP: PAULA, SAMUEL PLAÇA DE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2019.tde-09102019-020507
- Assunto: CIENCIA DA COMPUTACAO
- Keywords: Algoritmos de aproximação; Approximation algorithms; Clustering; Clustering; Combinatorial optimization; K-center; Otimização combinatória
- Agências de fomento:
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 19.12.2016
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
PAULA, Samuel Plaça de. Problema dos k-centros e variantes. 2016. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2016. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/. Acesso em: 10 abr. 2026. -
APA
Paula, S. P. de. (2016). Problema dos k-centros e variantes (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/ -
NLM
Paula SP de. Problema dos k-centros e variantes [Internet]. 2016 ;[citado 2026 abr. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/ -
Vancouver
Paula SP de. Problema dos k-centros e variantes [Internet]. 2016 ;[citado 2026 abr. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
