Probabilistic analysis of local search and NP-completeness result for constraint satisfaction

DOI10.1007/3-540-61332-3_171zbMath1529.68283OpenAlexW1608836784MaRDI QIDQ6184682

Hoong Chuin Lau

Publication date: 29 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61332-3_171

Mathematics Subject Classification ID

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)

Cites Work

• A guided tour of Chernoff bounds
• On the greedy algorithm for satisfiability
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• A spectral technique for coloring random 3-colorable graphs (preliminary version)
• On the minimality and global consistency of row-convex constraint networks
• Analytic Inequalities

This page was built for publication: Probabilistic analysis of local search and NP-completeness result for constraint satisfaction