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.

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, JAN 2 2017. (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, NOV 2015. (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, OCT 2016. (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., 2017-01-02. (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.