Towards a characterization of constant-factor approximable min CSPs

DOI10.1137/1.9781611973730.58zbMATH Open1371.90116OpenAlexW4256040681MaRDI QIDQ5362995FDOQ5362995

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

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 (11)

• On regularity of Max-CSPs and Min-CSPs
• Fixed-parameter Approximability of Boolean MinCSPs
• The power of linear programming for general-valued CSPs
• Title not available (Why is that?)
• The power of Sherali-Adams relaxations for general-valued CSPs
• Sherali-Adams relaxations for valued CSPs
• 2 CSPs all are approximable within a constant differential factor
• 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)