Towards a characterization of constant-factor approximable min CSPs

DOI10.1137/1.9781611973730.58MaRDI QIDQ5362995zbMATH OpenOpenAlexFDO

Authors Víctor Dalmau, Andrei Krokhin, Rajsekar Manokaran

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.58

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Towards a characterization of constant-factor approximable finite-valued CSPs
• Approximating CSPs using LP relaxation
• Fixed-parameter Approximability of Boolean MinCSPs
• From weak to strong LP gaps for all CSPs
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP

Cited in

(11)

• On regularity of Max-CSPs and Min-CSPs
• Fixed-parameter Approximability of Boolean MinCSPs
• The power of linear programming for general-valued CSPs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• The power of Sherali-Adams relaxations for general-valued CSPs
• 2 CSPs all are approximable within a constant differential factor
• Sherali-Adams relaxations for valued CSPs
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Approximating CSPs using LP relaxation
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• Robust algorithms with polynomial loss for near-unanimity CSPs

This page was built for publication: Towards a characterization of constant-factor approximable min CSPs

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