On bounded occurrence constraint satisfaction

DOI10.1016/S0020-0190(00)00032-6MaRDI QIDQ1607037zbMATH OpenOpenAlexWikidataFDO

Authors Johan Hastad

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)

Recommendations

• Every 2-CSP allows nontrivial approximation
• Every 2-CSP allows nontrivial approximation
• scientific article; zbMATH DE number 1303558
• Near-optimal algorithms for maximum constraint satisfaction problems
• On the efficient approximability of constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• scientific article; zbMATH DE number 1305390 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Approximation algorithms for combinatorial problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Optimization, approximation, and complexity classes

Cited in

(7)

• Computing the partition function of a polynomial on the Boolean cube
• SVARs with occasionally-binding constraints
• Local search is better than random assignment for bounded occurrence ordering \(k\)-CSPs
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• On the efficient approximability of constraint satisfaction problems
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Approximating Bounded Occurrence Ordering CSPs

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

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