2 CSPs all are approximable within a constant differential factor

DOI10.1007/978-3-319-96151-4_33zbMATH Open1401.90182OpenAlexW2883673176MaRDI QIDQ1661912FDOQ1661912

Authors: Jean-François Culus, Sophie Toulouse 

Publication date: 17 August 2018

Full work available at URL: https://hal.univ-antilles.fr/hal-02350144/file/ISCO2018_paper_91.pdf

Recommendations

• Towards a characterization of constant-factor approximable min CSPs
• Every 2-CSP allows nontrivial approximation
• Every 2-CSP allows nontrivial approximation
• Towards a characterization of constant-factor approximable finite-valued CSPs
• The approximability of constraint satisfaction problems

zbMATH Keywords

combinatorial designsdifferential approximationapproximation-preserving reductionsoptimization constraint satisfaction problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (2)

• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Every 2-CSP allows nontrivial approximation

This page was built for publication: 2 CSPs all are approximable within a constant differential factor

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