Sökning: onr:"swepub:oai:research.chalmers.se:ef8fdc23-2a2a-4202-9772-6da638b0f49f" >
Approximating linea...
Approximating linear threshold predicates
-
- Cheraghchi, M. (författare)
- Carnegie Mellon University (CMU)
-
- Håstad, Johan (författare)
- KTH,Teoretisk datalogi, TCS,Kungliga Tekniska Högskolan (KTH),Royal Institute of Technology (KTH)
-
- Isaksson, Marcus, 1978 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology,Göteborgs universitet,University of Gothenburg
-
visa fler...
-
- Svensson, Ola, 1971 (författare)
- Ecole Polytechnique Federale de Lausanne (EPFL),Swiss Federal Institute of Technology in Lausanne (EPFL)
-
visa färre...
-
(creator_code:org_t)
- 2012-03
- 2012
- Engelska.
-
Ingår i: ACM Transactions on Computation Theory. - : Association for Computing Machinery (ACM). - 1942-3462 .- 1942-3454. ; 4:1
- Relaterad länk:
-
https://eccc.weizman...
-
visa fler...
-
https://doi.org/10.1...
-
https://research.cha...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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 article is to identify and study the approximation curve of a class of threshold predicates that allow for nontrivial 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Matematisk analys (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Mathematical Analysis (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Approximation algorithms
- Linear threshold predicates
- Constraint satisfactory problems
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas