The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems

DOI10.1137/20M1312745zbMath1496.68255arXiv1907.04383OpenAlexW3109442675MaRDI QIDQ5138784

Marcin Wrochna, Joshua Brakensiek, Stanislav Živný, Venkatesan Guruswami

Publication date: 4 December 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.04383

zbMATH Keywords

algorithmslinear programminglinear equationsCSPpolymorphismspromise CSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)

Related Items (6)

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Local–global property for G-invariant terms ⋮ Sandwiches for promise constraint satisfaction ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization.
• The wonderland of reflections
• Linear programming, width-1 CSPs, and robust satisfaction
• Logical compactness and constraint satisfaction problems
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Improved hardness for H-colourings of G-colourable graphs
• How to Round Any CSP
• Algebraic approach to promise constraint satisfaction
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• $(2+\varepsilon)$-Sat Is NP-hard
• The complexity of satisfiability problems
• A Simple Algorithm for Mal'tsev Constraints

This page was built for publication: The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems