Approximating Linear Threshold Predicates

Cheraghchi, M.Ecole Polytechnique Federale de Lausanne (EPFL),Swiss Federal Institute of Technology in Lausanne (EPFL) (author)

QC 20120207
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(w1 x1+⋯+wn 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+⋯+xn ), 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.

Håstad, JohanKTH,Numerisk Analys och Datalogi, NADA(Swepub:kth)u1demvyb (author)
Isaksson, Marcus,1978Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematisk statistik,Department of Mathematical Sciences, Mathematical Statistics,Chalmers tekniska högskola,Chalmers University of Technology,University of Gothenburg(Swepub:cth)maris (author)
Svensson, OlaKTH,Teoretisk datalogi, TCS(Swepub:kth)u1yvrwm0 (author)
Ecole Polytechnique Federale de Lausanne (EPFL)Numerisk Analys och Datalogi, NADA (creator_code:org_t)

In:Lecture Notes in Computer Science. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, 1-3 September 2010Berlin, Heidelberg : Springer Berlin Heidelberg6302, s. 110-1230302-97431611-33499783642153686

By the author/editor: Cheraghchi, M.; Håstad, Johan; Isaksson, Marcus ...; Svensson, Ola

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics; and Computational Ma ...

By the university: University of Gothenburg; Chalmers University of Technology; Royal Institute of Technology

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.