Change search
ReferencesLink to record
Permanent link

Direct link
Approximating Linear Threshold Predicates
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2010 (English)Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2010. 110-123 p.
, Lecture Notes in Computer Science, ISSN 0302-9743
Keyword [en]
Approximability, constraint satisfaction problems, linear threshold predicates
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-63006DOI: 10.1007/978-3-642-15369-3_9ISI: 000284820600009ScopusID: 2-s2.0-78149314209ISBN: 978-364215368-6ISBN: 3642153682OAI: diva2:481492
13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010)

QC 20120207

Available from: 2012-01-21 Created: 2012-01-21 Last updated: 2012-09-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, JohanSvensson, Ola
By organisation
Numerical Analysis and Computer Science, NADATheoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 43 hits
ReferencesLink to record
Permanent link

Direct link