2 CSPs all are approximable within a constant differential factor

DOI10.1007/978-3-319-96151-4_33MaRDI QIDQ1661912zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

combinatorial designsdifferential approximationapproximation-preserving reductionsoptimization constraint satisfaction problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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

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)