Approximation algorithm for non-Boolean MAX k-CSP

DOI10.1007/978-3-642-32512-0_22MaRDI QIDQ3167401zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Yury Makarychev

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_22

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Approximation algorithms (68W25) Semidefinite programming (90C22)

Recommendations

• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• Approximation of non-Boolean 2CSP
• Automata, Languages and Programming
• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems

Cited in

(10)

• A combinatorial algorithm for MAX CSP
• Simultaneous approximation of constraint satisfaction problems
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• Approximation of non-Boolean 2CSP
• scientific article; zbMATH DE number 1833417 (Why is no real title available?)
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Approximating dense MAX 2-CSPs
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• Automata, Languages and Programming
• An invariance principle for the multi-slice, with applications

This page was built for publication: Approximation algorithm for non-Boolean MAX \(k\)-CSP

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