Robust algorithms with polynomial loss for near-unanimity CSPs

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Dalmau, Víctor
• dc.contributor.author Kozik, Marcin
• dc.contributor.author Krokhin, Andrei
• dc.contributor.author Makarychev, Konstantin
• dc.contributor.author Makarychev, Yury
• dc.contributor.author Opršal, Jakub
• dc.date.accessioned 2020-02-19T15:49:29Z
• dc.date.available 2020-02-19T15:49:29Z
• dc.date.issued 2019
• dc.description.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.
• dc.description.sponsorship The first author's research was partially supported by MINECO under grant TIN2016-76573-C2-1-P and Maria de Maeztu Units of Excellence programme MDM-2015-0502. The fifth author's research was partially supported by NSF awards CAREER CCF-1150062 and IIS-1302662. The sixth author's research was supported by the European Research Council (grant agreement 681988, CSP-Infinity). The research of the second and sixth authors was partially supported by the National Science Centre Poland under grant UMO-2014/13/B/ST6/01812.
• dc.format.mimetype application/pdf
• dc.identifier.citation Dalmau V, Kozik M, Krokhin A, Makarychev K, Makarychev Y, Opršal J. Robust algorithms with polynomial loss for near-unanimity CSPs. SIAM J Sci Comput. 2019 Nov 26;48(6):1763-95. DOI: 10.1137/18M1163932
• dc.identifier.doi http://dx.doi.org/10.1137/18M1163932
• dc.identifier.issn 0097-5397
• dc.identifier.uri http://hdl.handle.net/10230/43659
• dc.language.iso eng
• dc.publisher SIAM (Society for Industrial and Applied Mathematics)
• dc.relation.ispartof SIAM Journal on Computing. 2019 Nov 26;48(6):1763-95
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/681988
• dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TIN2016-76573-C2-1-P
• dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/MDM-2015-0502
• dc.rights © Society for Industrial and Applied Mathematics
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri https://creativecommons.org/licenses/by/4.0/
• dc.subject.keyword Constraint satisfaction
• dc.subject.keyword Approximation algorithms
• dc.subject.keyword Robust algorithm
• dc.subject.keyword Near-unanimity polymorphism
• dc.title Robust algorithms with polynomial loss for near-unanimity CSPs
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion