How to Round Any CSP

DOI10.1109/FOCS.2009.74MaRDI QIDQ5171222zbMATH OpenOpenAlexFDO

Authors Prasad Raghavendra, David Steurer

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.74

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Boolean programming (90C09) Stochastic programming (90C15) Semidefinite programming (90C22)

Cited in

(18)

• Towards a characterization of constant-factor approximable finite-valued CSPs
• Semidefinite programming and constraint programming
• Properties of an approximability-related parameter on circular complete graphs
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• Approximability Distance in the Space of H-Colourability Problems
• Simultaneous approximation of constraint satisfaction problems
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• Iterated linear optimization
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• The complexity of conservative valued CSPs
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Bounded degree nonnegative counting CSP
• On the mysteries of MAX NAE-SAT
• Algorithmic persuasion with evidence
• On approximability of satisfiable k-CSPs: V
• Separating \textsc{max} 2-and, \textsc{max di-cut}, and \textsc{max cut}
• Triangles improve 0.878 approximation for Maxcut
• Extended formulation for CSP that is compact for instances of bounded treewidth

This page was built for publication: How to Round Any CSP

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