Md. Renesa Nizamee
Supervisor: Dr. Antonina Kolokolova
Department of Computer Science
Monday, August 27, 2012, 1:00 p.m., Room EN 2022
A natural question when dealing with problem that are NP hard to solve is whether it’s possible to compute a solution which is close enough to the optimal solution for practical purposes. The usual notion of closeness is that the value of the solution is not far from the optimal value; in this talk, we will focus on the generalization of this notion where closeness is defined with respect to a given distance function. This framework, named Structure approximation, was introduced in 2007 paper by Hamilton, Müller, van Rooij and Wareham, who posed the question of complexity of solving NPhard optimization problems in this setting.
In this talk we are going to examine the complexity of structure approximation and show that at least for some choices for distance function any non trivial structure approximation is as hard to compute as the original problem. We will survey the relevant results from other related problems and show how they relate to our problem. We will also survey the techniques that can be used to solve this problem to prove inapproximability results such as Error correcting codes.