[Metric 2011] Johan Hastad

-------
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)
-------
Workshop on Metric embeddings, algorithms  and hardness of approximation
January 17-21, 2011
-------
Jan 20, 15:00-16:00
Johan Hastad (KTH Stockholm)
Approximating Linear Threshold Predicates
-------
For a k-ary predicate P we have a corresponding constraint satisfaction problem Max-P where each constraint is P applied to a k-tuple of literals and the task is to find values of the variables in order to satisfy the maximal number of constraints.
For all interesting predicates P this problem is NP-hard and we study efficient approximation algorithms. We are interested in the case when P is a linear threshold predicate, the simplest example being majority of an odd number of variables.
In the case of majority we get an almost tight approximation ratio as a function of k and the results extend to predicates which are defined by linear forms with small integral weights.
An interesting question left open is whether there are linear threshold predicates that are "approximation resistant", which is defined by the property that no efficient approximation algorithm can achieve a approximation ratio that is better than the ratio obtained by simply picking an assignment at random.
This is joint work with Mahdi Cheraghchi, Marcus Isaksson and Ola Svensson