Advanced search
Start date
Betweenand

Approximation Algorithms for Facility Location Problems with Different Distance Functions

Grant number: 10/20710-4
Support type:Scholarships in Brazil - Doctorate
Effective date (Start): April 01, 2011
Effective date (End): July 31, 2014
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Flávio Keidi Miyazawa
Grantee:Lehilton Lelis Chaves Pedrosa
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated scholarship(s):12/17634-0 - Advanced algorithms for facility location, inventory management and other supply chain optimization problems, BE.EP.DR

Abstract

In this project, we are interested on the Facility Location Problems, on the k-Means and other related problems with different connection restrictions. Our interest will be mainly focused on the recent strategies developed for this problems, specially those that lead to good approximation factors and practical results. The area of Approximation Algorithms has been receiving vast attention from researchers of the optimization and theory of computing areas. Such algorithms deal mostly with NP-hard problems. For such problems, exact algorithms are inviable. There are several techniques for the development of approximation algorithms, and they are being used to obtain good approximations for location problems and others. Several approximation algorithms for problems such as the FLP and the TSP strongly depend on that the underlying distance functions are metrics. However, for some applications, the distance functions do not obey to the triangular inequality, such is the case of the k-Means, that uses the squared euclidean distance. One of the main objectives of this project is to study such problems using other distance functions, and to investigate the consequences to the approximation.

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
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. Web of Science Citations: 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. Web of Science Citations: 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. Web of Science Citations: 6.
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
PEDROSA, Lehilton Lelis Chaves. Algoritmos de aproximação para problemas de alocação de instalações e outros problemas de cadeia de fornecimento. 2014. Doctoral Thesis - Universidade Estadual de Campinas. Instituto de Computação.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.