CORMSIS Seminar Event

Abstract:

In the field of combinatorial optimisation, a distinction can be made between exact methods, which are guaranteed to find an optimal solution and prove that it is optimal, and heuristic methods, which find solutions that are likely to be "reasonably good", but without any quality guarantee.  Somewhere between them lie approximation algorithms , which are methods that run in polynomial time, but are guaranteed to return solutions of a certain quality.  This talk will give a gentle introduction to this area.  I will start with a formal definition of approximation algorithms and approximation schemes, then present some early examples from the literature, and then discuss some general principles that underlie many of the existing algorithms.  After that, we will look at some combinatorial optimisation problems for which nobody has yet found a good approximation algorithm, and discuss the progress that has been made on proving that some of these problems cannot be even approximated in polynomial time, unless P = NP.