TY - GEN

T1 - Robust algorithms with polynomial loss for near-unanimity CSPs

AU - Dalmau, Vctor

AU - Kozik, Marcin

AU - Krokhin, Andrei

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Opršal, Jakub

N1 - Funding Information:
Yury Makarychev was partially supported by NSF awards CAREER CCF-1150062 and IIS-1302662.

PY - 2017

Y1 - 2017

N2 - An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for CSP is called robust if it outputs an assignment satisfying a (1 g)-fraction of constraints on any (1 )-satisfiable instance, where the loss function g is such that g 0 as 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterised by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g = O((log log(1=)= log(1=). It is natural to ask when a better loss can be achieved: in particular, polynomial loss g = O(1=k) for some constant k. In this paper, we consider CSPs with a constraint language having a nearunanimity polymorphism. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in , while the other works for a special ternary near-unanimity operation called dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalisation of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semi definite programming relaxation for CSP.

AB - An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for CSP is called robust if it outputs an assignment satisfying a (1 g)-fraction of constraints on any (1 )-satisfiable instance, where the loss function g is such that g 0 as 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterised by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g = O((log log(1=)= log(1=). It is natural to ask when a better loss can be achieved: in particular, polynomial loss g = O(1=k) for some constant k. In this paper, we consider CSPs with a constraint language having a nearunanimity polymorphism. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in , while the other works for a special ternary near-unanimity operation called dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalisation of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semi definite programming relaxation for CSP.

UR - http://www.scopus.com/inward/record.url?scp=85016166883&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016166883&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.22

DO - 10.1137/1.9781611974782.22

M3 - Conference contribution

AN - SCOPUS:85016166883

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 340

EP - 357

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -