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

DOI10.1007/978-3-540-85363-3_7MaRDI QIDQ3541788zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The Nonapproximability of Non-Boolean Predicates
• scientific article; zbMATH DE number 1833417
• Near-optimal algorithms for maximum constraint satisfaction problems
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Approximation algorithm for non-Boolean MAX k-CSP

Cited in

(8)

• Semidefinite programming and constraint programming
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• The Nonapproximability of Non-Boolean Predicates
• scientific article; zbMATH DE number 1833417 (Why is no real title available?)
• The quest for strong inapproximability results with perfect completeness
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3541788)