Robust algorithms with polynomial loss for near-unanimity CSPs

DOI10.1137/1.9781611974782.22zbMath1410.68162OpenAlexW2949361196MaRDI QIDQ4575759

Konstantin Makarychev, Yury Makarychev, Marcin Kozik, Jakub Opršal, Victor Dalmau, Andrei A. Krokhin

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.22

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving CSPs Using Weak Local Consistency

This page was built for publication: Robust algorithms with polynomial loss for near-unanimity CSPs