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

Abstract

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.