2015/04/02 by Guy Kindler, Kindler, Guy, Alexandra Kolla +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1504.00681
openalex publication_date 2015/04/02 · arxiv created 2015/04/06 · arxiv updated 2015/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a polynomial time Ω ( \frac 1R log R ) approximate algorithm for Max 2CSP-R, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size R, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a 1/R-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming (SDP) and on a novel rounding technique. The SDP that we use has an almost-matching integrality gap.