Janka Chlebikova (University of Portsmouth)

In the last years tight bounds on the efficient approximability for several optimization problems have been achieved using the Probabilistic Checkable Proof theory. However, the current state of the PCP technique hardly allows to obtain similar results for restricted instances of combinatorial optimization problems (e.g., in bounded degree graphs or in intersection graphs of some geometric objects). In this talk we present some techniques which were used to obtain currently the best inapproximability results for the Maximum Independent Set problem and other graph optimization problems in intersection graphs of 3-dimensional boxes.