Busca avançada
Ano de início
Entree
Conteúdo relacionado

Algoritmos de aproximação para problemas de localização com diferentes funções de distância

Processo: 10/20710-4
Linha de fomento:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de abril de 2011
Vigência (Término): 31 de julho de 2014
Área do 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

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.

Publicações científicas
(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, JAN 2 2017. Citações Web of Science: 0.
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, OCT 2016. Citações Web of Science: 5.
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, NOV 2015. Citações Web of Science: 7.
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. Instituto de Computação.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.