Approximating Linear Threshold Predicates

We study constraint satisfaction problems on the domain {-1,1}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form sgn(w_1 x_1 + ... + w_n x_n) for some positive integer weights w_1, ..., w_n. Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this paper is to identify and study the approximation curve of a class of threshold predicates that allow for non-trivial approximation. Arguably the simplest such predicate is the Majority predicate sgn(x_1+ ... + x_n), for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.


Published in:
Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
Presented at:
13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Barcelona, Spain, September 1-3, 2010
Year:
2010
Publisher:
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa
Keywords:
Laboratories:




 Record created 2010-09-16, last modified 2018-03-18


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)