Approximation Algorithms

Most interesting optimization problems are NP-Hard. For such problems, unless P=NP, exact algorithms cannot be efficient. In the field of approximation algorithms, we take the reverse perspective: efficient algorithms cannot be exact. But if we naturally insist on efficient algorithms, how close can we get to an optimal solution? In this group we design efficient algorithms with provable guarantees on the distance between their output and the (unknown) optimal solution. Complementing this, we are also studying the limits of such algorithms.