Sökning: onr:"swepub:oai:gup.ub.gu.se/155045" >
Approximating Linea...
Approximating Linear Threshold Predicates
-
- Cheraghchi, M. (författare)
- Ecole Polytechnique Federale de Lausanne (EPFL),Swiss Federal Institute of Technology in Lausanne (EPFL)
-
- Håstad, Johan (författare)
- KTH,Numerisk Analys och Datalogi, NADA
-
- Isaksson, Marcus, 1978 (författare)
- Gothenburg 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
-
visa fler...
-
- Svensson, Ola (författare)
- KTH,Teoretisk datalogi, TCS
-
visa färre...
-
(creator_code:org_t)
- ISBN 9783642153686
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2010
- 2010
- Engelska.
-
Serie: Lecture Notes in Computer Science, 0302-9743
-
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 2010. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783642153686 ; 6302, s. 110-123
- Relaterad länk:
-
https://eccc.weizman...
-
visa fler...
-
http://dx.doi.org/10...
-
https://gup.ub.gu.se...
-
https://doi.org/10.1...
-
https://research.cha...
-
https://urn.kb.se/re...
-
visa färre...
Innehållsförteckning
Abstract
Ämnesord
Stäng
No table of content available
- 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
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- Approximability
- constraint satisfaction problems
- linear threshold predicates
- linear threshold predicates
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas