Home / research areas / AA

Approximation Algorithms

Approximation Algorithms are algorithms with polynomial time complexity which find solutions with some quality assurance for Combinatorial Optimization problems. Approximation Algorithms are used to deal with NP-hard problems since, unless P=NP, there are no exact algorithms with polynomial time complexity for such problems. These algorithms have also been used for problems that, although they are not NP-hard, have exact polynomial algorithms very expensive.

In many situations it is better to sacrifice the optimality of the solution if it allows to obtain a solution in a timely manner. However, it is still desirable to have some quality assurance for the solution. Some techniques that have been used in approximation algorithms are: greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization.

Research in approximation algorithms can also lead to results inaproximabilidade to a problem. Quality assurance of the solutions obtained by polynomial algorithms for the problem in question are bounded by these results. This allows to classify problems NP-hard according to the difficulty of obtaining good approximations. Therefore, inaproximabilidade results are related to the study of complexity classes.


  • Bin Packing;
  • Facility Location;
  • Maximum Satisfiability;
  • Minimum Makespan Scheduling.
  • Travelling salesman;
  • Steiner Tree;


  • V. V. Vazirani. Approximation Algorithms. Springer, 2010. Amazon
  • D. S. Hochbaum. Approximation Algorithms for NP-Hard Problems. Course Technology, 1996. Amazon
  • D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Complete book, in PDF
  • M. H. de Carvalho, M. R. Cerioli, R. Dahab, P. Feofiloff, C. G. Fernandes, C. E. Ferreira, K. S. Guimarães, F. K. Miyazawa, J. C. de Pina Jr., J. A. R. Soares and Y. Wakabayashi. Uma Introdução Sucinta a Algoritmos de Aproximação. 23º Colóquio Brasileiro de Matemática, 2001. Complete book, in PDF

Professors (5):

  • Flávio Keidi Miyazawa
  • Lehilton Lelis Chaves Pedrosa
  • Orlando Lee
  • Rafael Crivellari Saliba Schouery
  • Santiago Valdés Ravelo