CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Approximating Linear Threshold Predicates

M. Cheraghchi ; J. Håstad ; Marcus Isaksson (Institutionen för matematiska vetenskaper, matematisk statistik) ; O. Svensson
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 (0302-9743). Vol. 6302 (2010), p. 110-123.
[Konferensbidrag, refereegranskat]

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.

Nyckelord: Approximability, constraint satisfaction problems, linear threshold predicates



Denna post skapades 2012-02-13. Senast ändrad 2016-08-18.
CPL Pubid: 155045

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematisk statistik (2005-2016)

Ämnesområden

Tillämpad matematik

Chalmers infrastruktur