Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four

DOI10.1007/978-3-642-32512-0_28zbMath1294.68088OpenAlexW2163430289MaRDI QIDQ3167407

Cenny Wenner

Publication date: 2 November 2012

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32512-0_28

zbMATH Keywords

NP-completenessconstraint satisfaction problemsapproximation resistance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

Approximation and complexity of multi-target graph search and the Canadian traveler problem

This page was built for publication: Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four