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)

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

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)