Algoritmos de aproximacao para problemas de particionamento

• Processo: 03/13815-0
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de julho de 2004
• Data de Término da vigência: 24 de fevereiro de 2008
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Flávio Keidi Miyazawa
• Beneficiário: Evandro Cesar Bracht
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmos De Aproximacao | Otimizacao Combinatoria | Problemas De Particionamento

Resumo

Algoritmos de aproximação é uma das áreas que tem recebido uma grande atenção dos pesquisadores de otimização e teoria da computação nos últimos anos. Isto se deve às novas técnicas que têm surgido, de caráter mais genérico, no desenvolvimento de algoritmos para problemas de otimização. Neste projeto estamos interessados em investigar problemas de particionamento, conhecido na literatura como "Clustering Problems", cuja função objetivo é particionar um dado conjunto de objetos de maneira que objetos "similares" pertençam à mesma parte, enquanto que objetos em partes distintas sejam menos "similares". Tais problemas aparecem na literatura de maneira bem variada, principalmente devido ao grande número de aplicações existentes, cada uma com uma definição apropriada da função de "similaridade". Buscaremos atacar tais problemas usando técnicas baseadas em algoritmos de aproximação e métodos probabilísticos. Nestas abordagens procuramos desenvolver algoritmos rápidos para problemas NP-difíceis, gerando soluções (com alta probabilidade) próximas da ótima. Muitas destas técnicas apresentam bons resultados quando aplicadas a instâncias práticas. Além disso, várias destas técnicas são recentes e mostram ser um excelente ponto de pesquisa. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

BRACHT, Evandro Cesar. Problemas de empacotamento com restrições de equilíbrio mecânico. 2016. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.