Advanced search
Start date

Exact and heuristic algorithms for solving difficult problems related to computational geometry

Grant number: 18/26434-0
Support type:Regular Research Grants
Duration: May 01, 2019 - October 31, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Pedro Jussieu de Rezende
Grantee:Pedro Jussieu de Rezende
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Assoc. researchers:Cid Carvalho de Souza


The goal of this proposal is to investigate solutions to several difficult combinatorial problems with the intent of obtaining both heuristics and exact methods that are, in practice, efficient for solving large instances. The problems considered are related to the area of computational geometry and most of them present geometric characteristics that, if properly exploited, will benefit the development of algorithms. The various techniques used stem mainly from combinatorial optimization (mathematical modeling, integer linear programming, column generation, cutting plane algorithms, Lagrangian relaxation), metaheuristics (such as GRASP, tabu search, among others), graph theory and polyhedral combinatorics. The research in this proposal lies in the field of theory of computing, with a strong component from design and analysis of algorithms, while also encompassing many aspects of experimental computation. (AU)