Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness

DOI10.1007/978-3-540-85363-3_7zbMath1159.68665OpenAlexW2165967486MaRDI QIDQ3541788

Prasad Raghavendra, Venkatesan Guruswami

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_7

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Unnamed Item ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ Semidefinite Programming and Constraint Programming ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness

This page was built for publication: Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness