Divide and concur: A general approach to constraint satisfaction

Details Divide and concur: A general approach to constraint satisfaction Divide and concur: A general approach to constraint satisfaction

2007-12-31

arxiv.org/abs/0801.0222v1

Phys. Rev. E 78, 036706 (2008)

Physics

Computational Physics

4 pages, 2 figures

Scientific paper

10.1103/PhysRevE.78.036706

Many difficult computational problems involve the simultaneous satisfaction of multiple constraints which are individually easy to satisfy. Such problems occur in diffractive imaging, protein folding, constrained optimization (e.g., spin glasses), and satisfiability testing. We present a simple geometric framework to express and solve such problems and apply it to two benchmarks. In the first application (3SAT, a boolean satisfaction problem), the resulting method exhibits similar performance scaling as a leading context-specific algorithm (walksat). In the second application (sphere packing), the method allowed us to find improved solutions to some old and well-studied optimization problems. Based upon its simplicity and observed efficiency, we argue that this framework provides a competitive alternative to stochastic methods such as simulated annealing.

Affiliated with

Also associated with

No associations

Rating

Divide and concur: A general approach to constraint satisfaction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Divide and concur: A general approach to constraint satisfaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Divide and concur: A general approach to constraint satisfaction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-235281