Linear programming, width-1 CSPs, and robust satisfaction

DOI10.1145/2090236.2090274zbMath1347.68184OpenAlexW2091694652MaRDI QIDQ2826079

Gábor Kun, Yuichi Yoshida, Yuan Zhou, Ryan O'Donnell, Suguru Tamaki

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2090236.2090274

zbMATH Keywords

linear programmingapproximation algorithmconstraint satisfaction problemsrobust satisfaction algorithmwidth-1 CSPs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Approximation algorithms (68W25)

Related Items (16)

CLAP: A New Algorithm for Promise CSPs ⋮ Approximating CSPs Using LP Relaxation ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ A new line of attack on the dichotomy conjecture ⋮ The Complexity of Valued CSPs ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ On algebras with many symmetric operations ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ The Power of Linear Programming for General-Valued CSPs

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

This page was built for publication: Linear programming, width-1 CSPs, and robust satisfaction