Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Robust algorithms with polynomial loss for near-unanimity CSPs.

Dalmau, V. and Kozik, M. and Krokhin, A. and Makarychev, K. and Makarychev, Y. and Oprsal, J. (2017) 'Robust algorithms with polynomial loss for near-unanimity CSPs.', in Proceedings of the twenty-eighth Annual ACM-SIAM symposium on discrete algorithms. , pp. 340-357.

Abstract

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 polynomialtime 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 near-unanimity polymorphism. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for Marcin Kozik and Jakub Oprˇsal were partially supported by the National Science Centre Poland under grant no. UMO- 2014/13/B/ST6/01812; Jakub Oprˇsal has also received fund- ing from the European Research Council (Grant Agreement no. 681988, CSP-Infinity). Yury Makarychev was partially supported by NSF awards CAREER CCF-1150062 and IIS- 1302662. 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 semidefinite programming relaxation for CSP.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(404Kb)
Full text:(VoR) Version of Record
Download PDF
(483Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1137/1.9781611974782.22
Publisher statement:Copyright © by SIAM
Date accepted:10 October 2016
Date deposited:16 December 2016
Date of first online publication:04 January 2017
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar