Approximation for Maximum Surjective Homomorphism Problem
Hang Zhou, École normale supérieure
29 April 2011, 14:00, Salle de conférences, LIX, Ecole Polytechnique

The maximum surjective homomorphism problem asks for a surjective function
h from the input relational structure A to some fixed template relational
structure B, such that the number of relational constraints in A preserved
by h is maximized.

We will show this problem is polynomial time approximable with some
constant ratio. Then we will try to get a more precise bound of the
approximation ratio for two important template relational structures.