About Randomized Approximation Algorithms.
Jaroslaw Byrka will defend his thesis:
Despite great effort, researchers are unable to find efficient algorithms for a number of natural computational problems. Typically, it is possible to emphasize the hardness of such problems by proving that they are at least as hard as a number of other problems. In the language of computational complexity it means proving that the problem is complete for a certain class of problems.
For optimization problems, we may consider to relax the requirement of the outcome to be optimal and accept an approximate (i.e., close to optimal) solution. For many problems that are hard to solve optimally, it is actually possible to efficiently find close to optimal solutions. In this thesis, Byrka studies algorithms for computing such approximate solutions.
Promotors:
Prof.dr. K.I. Aardal (Delft Univ. of Technology) and Prof.dr. M.T. de Berg (Eindhoven Univ. of Technology).
Location: Auditorium of the Eindhoven University of Technology, 16:00.
We cordially invite everyone interested to attend this ceremony.
