Approximation Algorithms for Facility Location Problems with Different Distance Functions

• Grant number: 10/20710-4
• Support Opportunities: 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
• Host 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

(4)

(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. (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)

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 (UNICAMP). Instituto de Computação Campinas, SP.