Towards a characterization of approximation resistance for symmetric CSPs

DOI10.4230/LIPICS.APPROX-RANDOM.2015.305MaRDI QIDQ5351908zbMATH OpenOpenAlexFDO

Authors Euiwoong Lee, Venkatesan Guruswami

Publication date 31 August 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2015/5309/pdf/19.pdf/

zbMATH Keywords

approximation resistanceconstraint satisfaction problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• Towards a characterization of approximation resistance for symmetric CSPs
• A characterization of approximation resistance for even k-partite CSPs
• A characterization of strong approximation resistance
• scientific article; zbMATH DE number 2019637
• Approximation resistance on satisfiable instances for predicates with few accepting inputs

Cited in

(4)

• A characterization of approximation resistance for even k-partite CSPs
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Towards a characterization of approximation resistance for symmetric CSPs
• A characterization of approximability for biased CSPs

This page was built for publication: Towards a characterization of approximation resistance for symmetric CSPs

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