Busca avançada
Ano de início
Entree

Algoritmos de Aproximação para Problemas de Localização com Diferentes Funções de Distância

Processo: 10/20710-4
Modalidade de apoio:Bolsas no Brasil - Doutorado
Data de Início da vigência: 01 de abril de 2011
Data de Término da vigência: 31 de julho de 2014
Á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:Lehilton Lelis Chaves Pedrosa
Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Bolsa(s) vinculada(s):12/17634-0 - Algoritmos avançados para alocação de recursos, gerência de estoque e outros problemas de cadeia de fornecimento, BE.EP.DR
Assunto(s):Algoritmos de aproximação
Palavra(s)-Chave do Pesquisador:Algoritmos de Aproximação | Funções de Distância | k-Means Clustering | Localização de Facilidades | Algoritmos de Aproximação

Resumo

Neste projeto, estamos interessados em investigar o Problema de Localização de Facilidades (FLP), k-Means e problemas correlatos com outras restrições de conectividade. Nosso interesse será focado em estratégias recentes desenvolvidas para estes problemas, principalmente aquelas que levam a bons fatores de aproximação e resultados práticos. Algoritmos de aproximação é uma das áreas que têm recebido grande atenção dos pesquisadores de otimização e teoria da computação nos últimos anos. Esses algoritmos são utilizados principalmente em problemas NP-difícies, para os quais um algoritmo exato seria inviável. Existem diferentes técnicas para o desenvolvimento de algoritmos de aproximação, que têm sido utilizadas para obter aproximações cada vez melhores para os problemas de localização e vários outros. Diversos algoritmos de aproximação para problemas, como o FLP ou o TSP, utilizam fortemente o fato de que as funções de distância subjacentes sejam métricas para obter resultados de aproximação. Para algumas aplicações, no entanto, as funções de distância não obedecem à desigualdade triangular, como é o caso do k-Means, que utiliza a distância euclidiana ao quadrado. Um dos principais objetivos deste projeto é investigar estes problemas usando outras funções de distância e investigaremos as consequências para a aproximação.

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas (4)
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
MEIRA, LUIS A. A.; MIYAZAWA, FLAVIO K.; PEDROSA, LEHILTON L. C.. Clustering through Continuous Facility Location Problems. THEORETICAL COMPUTER SCIENCE, v. 657, n. B, p. 137-145, . (10/20710-4)
FERNANDES, CRISTINA G.; MEIRA, LUIS A. A.; MIYAZAWA, FLAVIO K.; PEDROSA, LEHILTON L. C.. A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. MATHEMATICAL PROGRAMMING, v. 153, n. 2, p. 655-685, . (10/20710-4)
MIYAZAWA, FLAVIO K.; PEDROSA, LEHILTON L. C.; SCHOUERY, RAFAEL C. S.; SVIRIDENKO, MAXIM; WAKABAYASHI, YOSHIKO. Polynomial-Time Approximation Schemes for Circle and Other Packing Problems. ALGORITHMICA, v. 76, n. 2, p. 536-568, . (10/20710-4, 13/03447-6, 13/21744-8, 13/02434-8)
MEIRA, LUIS A. A.; MIYAZAWA, FLAVIO K.; PEDROSA, LEHILTON L. C.. Clustering through Continuous Facility Location Problems. THEORETICAL COMPUTER SCIENCE, v. 657, p. 9-pg., . (10/20710-4)
Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
PEDROSA, Lehilton Lelis Chaves. Approximation algorithms for facility location problems and other supply chain problems. 2014. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.