###### 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.

### Problems:

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

### References:

- 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