Linear programming, width-1 CSPs, and robust satisfaction
From MaRDI portal
Publication:2826079
DOI10.1145/2090236.2090274zbMath1347.68184MaRDI QIDQ2826079
Gábor Kun, Yuichi Yoshida, Yuan Zhou, Suguru Tamaki, Ryan O'Donnell
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
linear programming; approximation algorithm; constraint satisfaction problems; robust satisfaction algorithm; width-1 CSPs
68Q25: Analysis of algorithms and problem complexity
90C05: Linear programming
68W25: Approximation algorithms