Advanced search
Start date

Approximation algorithms

Grant number: 19/13311-0
Support Opportunities:Scholarships in Brazil - Scientific Initiation
Effective date (Start): September 01, 2019
Effective date (End): August 31, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Carla Negri Lintzmayer
Grantee:Wesley Lima de Araujo
Host Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil


In a combinatorial optimization problem the objective is to find a solution of minimum or maximum cost among all possible solutions. Normally, these kind of problems are NP-hard, so there is no hope in finding an algorithm that solves the problems in polynomial time. An approximation algorithm is an algorithm that runs in polynomial time and returns a solution whose cost is at most a factor distant of the optimal one. Unfortunately, there is no recipe to build algorithms for combinatorial optimization problems and even less to prove their approximation factor. The objective of this project is to introduce the student to the research in the area of Combinatorial Optimization by studying different classic approximation algorithms and their techniques.

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

Please report errors in scientific publications list by writing to: