We develop basic best-first and depth-first search algorithms for providing upper and lower bounds on the partition function in an anytime manner. We also develop an ϵ-guarantee depth- first search scheme for OR and AND/OR search trees that corresponds to a given graphical model.