Skip to main content

Research Repository

Advanced Search

Robust algorithms with polynomial loss for near-unanimity CSPs

Dalmau, V.; Kozik, M.; Krokhin, A.; Makarychev, K.; Makarychev, Y.; Oprsal, J.

Robust algorithms with polynomial loss for near-unanimity CSPs Thumbnail


Authors

V. Dalmau

M. Kozik

K. Makarychev

Y. Makarychev

J. Oprsal



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 xed domain to the variables so that all constraints are satised. In the optimization version, the goal is to maximize the number of satised constraints. An approximation algorithm for CSP is called robust if it outputs an assignment satisfying an (1????g("))-fraction of constraints on any (1????")-satisable 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, specically 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. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. 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 xed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidenite programming relaxation for CSP.

Citation

Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2019). Robust algorithms with polynomial loss for near-unanimity CSPs. SIAM Journal on Computing, 48(6), 1763-1795. https://doi.org/10.1137/18m1163932

Journal Article Type Article
Acceptance Date Sep 4, 2019
Online Publication Date Nov 26, 2019
Publication Date 2019
Deposit Date Sep 6, 2019
Publicly Available Date Nov 28, 2019
Journal SIAM Journal on Computing
Print ISSN 0097-5397
Electronic ISSN 1095-7111
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 48
Issue 6
Pages 1763-1795
DOI https://doi.org/10.1137/18m1163932

Files

Published Journal Article (549 Kb)
PDF

Copyright Statement
© 2019, Society for Industrial and Applied Mathematics.





You might also like



Downloadable Citations