Statistical regimes across constrainedness regions

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

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

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 transitionsheavy-tailed distributionsbacktrack searchruntime distributionstypical case analysis

Mathematics Subject Classification ID

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

Related Items (6)

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

Uses Software

• Chaff

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Statistical regimes across constrainedness regions