Sökning: L773:0302 9743 OR L773:1611 3349 OR L773:9783540407263 >
Approximating Linea...
-
Cheraghchi, M.Ecole Polytechnique Federale de Lausanne (EPFL),Swiss Federal Institute of Technology in Lausanne (EPFL)
(författare)
Approximating Linear Threshold Predicates
- Artikel/kapitelEngelska2010
Förlag, utgivningsår, omfång ...
-
Berlin, Heidelberg :Springer Berlin Heidelberg,2010
Nummerbeteckningar
-
LIBRIS-ID:oai:gup.ub.gu.se/155045
-
ISBN:9783642153686
-
ISBN:3642153682
-
https://gup.ub.gu.se/publication/155045URI
-
https://doi.org/10.1007/978-3-642-15369-3_9DOI
-
https://research.chalmers.se/publication/155045URI
-
https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-63006URI
Kompletterande språkuppgifter
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:kon swepub-publicationtype
Serie
-
Lecture Notes in Computer Science,0302-9743
Anmärkningar
-
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.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Håstad, JohanKTH,Numerisk Analys och Datalogi, NADA(Swepub:kth)u1demvyb
(författare)
-
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
(författare)
-
Svensson, OlaKTH,Teoretisk datalogi, TCS(Swepub:kth)u1yvrwm0
(författare)
-
Ecole Polytechnique Federale de Lausanne (EPFL)Numerisk Analys och Datalogi, NADA
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i: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
Internetlänk
Hitta via bibliotek
Till lärosätets databas