Huang, Neng ;
Potechin, Aaron
On the Approximability of Presidential Type Predicates
Abstract
Given a predicate P: {1, 1}^k → {1, 1}, let CSP(P) be the set of constraint satisfaction problems whose constraints are of the form P. We say that P is approximable if given a nearly satisfiable instance of CSP(P), there exists a probabilistic polynomial time algorithm that does better than a random assignment. Otherwise, we say that P is approximation resistant.
In this paper, we analyze presidential type predicates, which are balanced linear threshold functions where all of the variables except the first variable (the president) have the same weight. We show that almost all presidential type predicates P are approximable. More precisely, we prove the following result: for any δ₀ > 0, there exists a k₀ such that if k ≥ k₀, δ ∈ (δ₀,1  2/k], and {δ}k + k  1 is an odd integer then the presidential type predicate P(x) = sign({δ}k{x₁} + ∑_{i = 2}^{k} {x_i}) is approximable. To prove this, we construct a rounding scheme that makes use of biases and pairwise biases. We also give evidence that using pairwise biases is necessary for such rounding schemes.
BibTeX  Entry
@InProceedings{huang_et_al:LIPIcs:2020:12661,
author = {Neng Huang and Aaron Potechin},
title = {{On the Approximability of Presidential Type Predicates}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {58:158:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12661},
URN = {urn:nbn:de:0030drops126612},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.58},
annote = {Keywords: constraint satisfaction problems, approximation algorithms, presidential type predicates}
}
11.08.2020
Keywords: 

constraint satisfaction problems, approximation algorithms, presidential type predicates 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 