On bounded occurrence constraint satisfaction

DOI10.1016/S0020-0190(00)00032-6zbMath1014.68149OpenAlexW2091260378WikidataQ56959043 ScholiaQ56959043MaRDI QIDQ1607037

Johan T. Håstad

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00032-6

zbMATH Keywords

constraint satisfaction problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (2)

Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ Computing the Partition Function of a Polynomial on the Boolean Cube

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• A threshold of ln n for approximating set cover
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: On bounded occurrence constraint satisfaction