Advanced search
Start date

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


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)

Articles published in Agência FAPESP Newsletter about the research grant:
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)
SAPUCAIA, ALLAN; REZENDE, PEDRO J. DE; SOUZA, CID C. DE. Solving the minimum convex partition of point sets with integer programming. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v. 99, . (18/14883-5, 18/26434-0, 14/12236-1)

Please report errors in scientific publications list by writing to: