Towards a characterization of approximation resistance for symmetric CSPs

DOI10.4230/LIPICS.APPROX-RANDOM.2015.305zbMATH Open1375.68103OpenAlexW2285292888MaRDI QIDQ5351908FDOQ5351908

Venkatesan Guruswami, Euiwoong Lee

Publication date: 31 August 2017

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

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

zbMATH Keywords

constraint satisfaction problemsapproximation resistance

Mathematics Subject Classification ID

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

Cited In (2)

• A characterization of approximability for biased CSPs
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

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)