Advanced search
Start date

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

Grant number: 12/17634-0
Support Opportunities: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: Maxim Sviridenko
Host 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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

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, . (12/17634-0)
PEDROSA, LEHILTON L. C.; SVIRIDENKO, MAXIM; PARDO, A; VIOLA, A. Integrated Supply Chain Management via Randomized Rounding. LATIN 2014: THEORETICAL INFORMATICS, v. 8392, p. 12-pg., . (12/17634-0)

Please report errors in scientific publications list using this form.