Statistical regimes across constrainedness regions

DOI10.1007/s10601-005-2807-zzbMath1102.68651MaRDI QIDQ850446

Christian Bessiere, Carla P. Gomes, Cèsar Fernández, Bart Selman

Publication date: 3 November 2006

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10459.1/57603

zbMATH Keywords

phase transitions; heavy-tailed distributions; backtrack search; runtime distributions; typical case analysis

Mathematics Subject Classification ID

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

Related Items

Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, The impact of search heuristics on heavy-tailed behaviour, A generative power-law search tree model, A global constraint for total weighted completion time for unary resources, Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms]

Uses Software

• Chaff

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The hardest constraint problems: A double phase transition
• Easy problems are sometimes hard
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• Resolution versus search: Two strategies for SAT
• Theory and Applications of Satisfiability Testing
• Random constraint satisfaction: A more accurate picture