Robust algorithms with polynomial loss for near-unanimity CSPs

Víctor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Opršal

Research output: Contribution to journalArticle

1 Scopus citations

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 a CSP is called robust if it outputs an assignment satisfying an (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 characterized 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. 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 the dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalization 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 the CSP.

Original languageEnglish (US)
Pages (from-to)1763-1795
Number of pages33
JournalSIAM Journal on Computing
Volume48
Issue number6
DOIs
StatePublished - 2019

Keywords

  • Approximation algorithms
  • Constraint satisfaction
  • Near-unanimity polymorphism
  • Robust algorithm

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Robust algorithms with polynomial loss for near-unanimity CSPs'. Together they form a unique fingerprint.

  • Cite this

    Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Opršal, 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