Branch And Bound

Old ComputerScientist algorithm trick.

Basically, it's a way of looking for a needle in a haystack: you recursively search the entire haystack (to search some hay, split it in half and search each half), but before searching each bit, you see if you can rule it out a priori (typically, in optimisation problems, by showing that it cannot contain any solution better than the best one found so far).

• http://www.nist.gov/dads/HTML/branchNbound.html
• http://en.wikipedia.org/wiki/Branch_and_bound
• http://www.csulb.edu/~obenli/Research/IE-encyc/bb.html
• http://www.cs.sandia.gov/opt/survey/branch-and-bound.html

---

CategoryAlgorithm