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