Linear programming, width-1 CSPs, and robust satisfaction

DOI10.1145/2090236.2090274MaRDI QIDQ2826079zbMATH OpenOpenAlexFDO

Authors Gabor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou

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

approximation algorithmconstraint satisfaction problemslinear programmingrobust satisfaction algorithmwidth-1 CSPs

Mathematics Subject Classification ID

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

Recommendations

• Robustly solvable constraint satisfaction problems
• Robust satisfiability for CSPs: hardness and algorithmic results
• Robust satisfiability of constraint satisfaction problems
• An LP-Designed Algorithm for Constraint Satisfaction
• The power of linear programming for general-valued CSPs

Cites work

• Asymptotic calibration
• Dimension in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• scientific article; zbMATH DE number 3227613 (Why is no real title available?)
• The Complexity of Forecast Testing
• The dimensions of individual strings and sequences
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• The reproducible properties of correct forecasts
• The Well-Calibrated Bayesian
• Universal prediction

Cited in

(25)

• Towards a characterization of constant-factor approximable finite-valued CSPs
• Dismantlability, connectedness, and mixing in relational structures
• Robustly solvable constraint satisfaction problems
• On algebras with many symmetric operations
• Robust satisfiability for CSPs: hardness and algorithmic results
• Approximating CSPs using LP relaxation
• Sherali-Adams relaxations for valued CSPs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• The complexity of valued CSPs
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Dismantlability, Connectedness, and Mixing in Relational Structures
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• Robust algorithms with polynomial loss for near-unanimity CSPs
• The power of linear programming for general-valued CSPs
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The power of Sherali-Adams relaxations for general-valued CSPs
• Robust satisfiability of constraint satisfaction problems
• CLAP: A New Algorithm for Promise CSPs
• Bi-arc digraphs: recognition algorithm and applications
• The complexity of the distributed constraint satisfaction problem
• Promise and infinite-domain constraint satisfaction
• Sketching approximability of all finite CSPs
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• The complexity of the distributed constraint satisfaction problem
• A new line of attack on the dichotomy conjecture

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

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