| 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 |
| Local de pesquisa : | University of Warwick, England |
| Associated to the scholarship: | 10/20710-4 - Approximation Algorithms for Facility Location Problems with Different Distance Functions, BP.DR |
Abstract 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) | |