Near-optimal algorithms for maximum constraint satisfaction problems

DOI10.1145/1541885.1541893MaRDI QIDQ2930257zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Yury Makarychev, Moses Charikar

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1541885.1541893

zbMATH Keywords

\textsc{MAX \(k\)-CSP}\textsc{MAX 2CSP}\textsc{SDP}

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 6381632
• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem
• Automata, Languages and Programming
• On the efficient approximability of constraint satisfaction problems
• scientific article; zbMATH DE number 1552232
• scientific article; zbMATH DE number 1258327
• The approximability of constraint satisfaction problems
• Algorithms for the maximum satisfiability problem

Cited in

(39)

• A combinatorial algorithm for MAX CSP
• On bounded occurrence constraint satisfaction
• An efficient algorithm for a class of constraint satisfaction problems
• Solving RCPSP/max by lazy clause generation
• The approximability of constraint satisfaction problems
• Semidefinite programming and constraint programming
• Robustly solvable constraint satisfaction problems
• Near-optimal algorithms for unique games
• scientific article; zbMATH DE number 6381632 (Why is no real title available?)
• Explicit optimal hardness via Gaussian stability results
• Exact and approximation algorithms for the maximum constraint satisfaction problem over the point algebra
• Approximation algorithms for unique games
• Black-box reductions in mechanism design
• Approximation algorithm for non-Boolean MAX k-CSP
• Designing FPT algorithms for cut problems using randomized contractions
• Simultaneous approximation of constraint satisfaction problems
• Maximum Constraint Satisfaction on Diamonds
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• scientific article; zbMATH DE number 2119703 (Why is no real title available?)
• Re-optimization of constraint satisfaction problems with predicates of arity two
• Approximation Algorithms for CSPs
• The quest for strong inapproximability results with perfect completeness
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The power of Sherali-Adams relaxations for general-valued CSPs
• Beating the random assignment on constraint satisfaction problems of bounded degree
• Fast SDP algorithms for constraint satisfaction problems
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• An LP-Designed Algorithm for Constraint Satisfaction
• Automata, Languages and Programming
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• The maximum feasible subset problem (maxFS) and applications
• SDPs and robust satisfiability of promise CSP
• An invariance principle for the multi-slice, with applications
• On approximability of satisfiable k-CSPs: V

This page was built for publication: Near-optimal algorithms for maximum constraint satisfaction problems

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