transparent gif


Ej inloggad.

Göteborgs universitets publikationer

Approximating Linear Threshold Predicates

Författare och institution:
M. Cheraghchi (-); J. Håstad (-); Marcus Isaksson (Institutionen för matematiska vetenskaper, matematisk statistik, Chalmers/GU); O. Svensson (-)
Publicerad 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, 6302 s. 110-123
Konferensbidrag, refereegranskat
Sammanfattning (abstract):
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.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
Matematik ->
Beräkningsmatematik ->
Tillämpad matematik
Approximability, constraint satisfaction problems, linear threshold predicates
Postens nummer:
Posten skapad:
2012-02-13 11:23
Posten ändrad:
2016-08-18 13:32

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007