Towards a characterization of constant-factor approximable min CSPs

DOI10.1137/1.9781611973730.58zbMATH Open1371.90116OpenAlexW4256040681MaRDI QIDQ5362995FDOQ5362995

Rajsekar Manokaran, Andrei Krokhin, Víctor Dalmau

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• Approximating CSPs Using LP Relaxation
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
• Fixed-parameter Approximability of Boolean MinCSPs
• Title not available (Why is that?)
• The Power of Linear Programming for General-Valued CSPs
• Sherali-Adams Relaxations for Valued 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)