Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743
Keyword [en]
Approximability, constraint satisfaction problems, linear threshold predicates
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-63006DOI: 10.1007/978-3-642-15369-3_9ISI: 000284820600009Scopus ID: 2-s2.0-78149314209ISBN: 978-364215368-6 ISBN: 3642153682 (print)OAI: oai:DiVA.org:kth-63006DiVA: diva2:481492
Conference
13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010)
Note

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

Authority records BETA

Håstad, Johan

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 51 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf