Under the strongly believed conjecture that P is not NP, no polynomial time exact algorithms exist for many important problems. However, suboptimal solutions (which run in polynomial time) are most of the time sufficient for practical applications. Moreover, approximation algorithms allow us to explore the structure of NP-hard problems and distinguish between different levels of difficulty that these problems exhibit in theory and practice.

In this talk I attempt to give an overview of the most famous results in the field of approximation algorithms. Interestingly, many problems which seem unrelated at the first sight can be tackled using similar techniques. Thus, I will also survey the main methods used so far to derive approximation algorithms and to prove hardness of approximation.

In the last part I will present part of my recent work. I will show some novel results regarding NP-hard problems with applications in areas such as wireless networks, computational biology and pattern matching.