Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

CORMSIS Seminar Event

16:00 - 17:00
24 February 2015
Room 06/1083

For more information regarding this event, please telephone Tri-Dung Nguyen on +27759 or email .

Event details

An Introduction to Approximation Algorithms (and Inapproximability)


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.

Speaker information

Adam Letchford,Lancaster University,Adam N. Letchford is known internationally for his research on exact solution methods for NP-hard optimisation problems. He is known especially for his work in three areas: the travelling salesman problem, vehicle routing problems, and cutting plane theory. He has been the recipient of an IBM Faculty Award and an EPSRC Advanced Research Fellowship, and is a Fellow of the Operational Research Society. He has been on the editorial boards of six journals: Computational Optimisation and Applications, Discrete Optimization, EURO Journal of Computational Optimization, Mathematical Programming, Mathematical Programming Computation and Operations Research. From 2008-2014, he was the coordinator of the optimisation cluster of the LANCS Initiative.

Privacy Settings