Algorithms for packing and graph problems

• Grant number: 08/01490-3
• Support Opportunities: Regular Research Grants
• Start date: May 01, 2008
• End date: April 30, 2010
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Eduardo Candido Xavier
• Grantee: Eduardo Candido Xavier
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project we are interested in the study of packing and graph problems. In packing problems we must have to pack items into bins under some constraints maximizing or minimizing some objective function. Packing problems have many applications in several areas like cutting stock problems, logistics and scheduling problems in computer science. We are also interested in the study of combinatorial optimization problems that can be formulated as graph problems, especially problems related to network design, and problems that join packing and graph problems. One example of such a problem is the one that we must have to distribute merchandise among clients using trucks. This problem involves a packing problem with routing problem. Our objective is to design new algorithms for combinatorial optimization problems that can be formulated as packing problems and graph 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)

XAVIER, EDUARDO C.; MIYAZAWA, FLAVIO KEIDI. A NOTE ON DUAL APPROXIMATION ALGORITHMS FOR CLASS CONSTRAINED BIN PACKING PROBLEMS. RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, v. 43, n. 2, p. 239-248, APR-JUN 2009. (08/01490-3)