Problema dos k-centros e variantes (2016)
- Authors:
- Autor USP: PAULA, SAMUEL PLAÇA DE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- 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
-
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: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/. Acesso em: 16 fev. 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 http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/ -
NLM
Paula SP de. Problema dos k-centros e variantes [Internet]. 2016 ;[citado 2026 fev. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/ -
Vancouver
Paula SP de. Problema dos k-centros e variantes [Internet]. 2016 ;[citado 2026 fev. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09102019-020507/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
