Advanced search
Start date

Advanced algorithms for facility location, inventory management and other supply chain optimization problems

Grant number: 12/17634-0
Support type:Scholarships abroad - Research Internship - Doctorate
Effective date (Start): February 01, 2013
Effective date (End): January 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
Supervisor abroad: Maxim Sviridenko
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Research place: University of Warwick, England  
Associated to the scholarship:10/20710-4 - Approximation Algorithms for Facility Location Problems with Different Distance Functions, BP.DR


Approximation algorithms have received great attention from the research community working on optimization and computer theory. Such algorithms are mainly used to solve NP-hard problems, for which no exact algorithm would be viable. There are several techniques used to obtain approximations for the facility location problem and others. Usually, these techniques can be used when dealing with variants of the classical metric FLP, and other supply chain problems. In this project, we are interested in the Facility Location Problem (FLP), variants, and other supply chain problems, such as the Inventory Management Problem. Our focus we be in recent techniques developed for this problems, especially those used to obtain good approximation factors. Among such techniques are the LP-rounding and the primal-dual technique. In particular, the primal-dual combined with the analysis through the factor-reveling programs. A first objective of this project is to study these techniques, and apply them to some of these variants and related problems.We also want to investigate different distance functions for the studied problems. Many approximation algorithms for problems such as the FLP or the TSP, and the corresponding analyses, are strongly based on the assumption that the underling distance functions are metric. For some applications, however, the distances function do not obey to the triangle inequality, such as the k-means, based on the squared Euclidean distance. The TSP and the FLP have already been considered for non-metric distance functions. Another objective of this work is to further extend this study of the FLP to other variants and related problems. (AU)

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)
PEDROSA, LEHILTON L. C.; SVIRIDENKO, MAXIM. Integrated Supply Chain Management via Randomized Rounding. INFORMS JOURNAL ON COMPUTING, v. 30, n. 1, p. 124-136, WIN 2018. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: